ECKCDSA von JavaScript zu VB.NET

evolver · 31. März 2021, 11:21

Hallo,
nachdem ich jetzt eine funktionierende Curve25519 habe brauche ich noch einmal eure Unterstützung. Ich möchte nun messages mit dem EC-KCDSA (Elliptic Curve Korean Certificate-based Digital Signature Algorithm) Verfahren signieren und verifizieren. Das Signieren läuft bereits bestens nur das Verifizieren noch nicht so ganz. Ich finde dafür nun allerdings auch keine passenden Quellcodes, die man nahezu 1zu1 übersetzen kann. Lediglich eine JavaScript-Variante die wohl leider keine Longs hat und stattdessen alles mit UInt16Arrays rechnet:

Spoiler anzeigen

Quellcode

/* Signature verification primitive, calculates Y = vP + hG
* v [in] signature value
* h [in] signature hash
* P [in] public key
* Returns signature public key
*/
public static verify(v, h, P) {
/* Y = v abs(P) + h G */
let d = new Array(32);
let p = [Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray()];
let s = [Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray()];
let yx = [Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray()];
let yz = [Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray()];
let t1 = [Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray()];
let t2 = [Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray(), Curve25519.createUnpackedArray()];
let vi = 0, hi = 0, di = 0, nvh = 0, i, j, k;
/* set p[0] to G and p[1] to P */
Curve25519.set(p[0], 9);
Curve25519.unpack(p[1], P);
/* set s[0] to P+G and s[1] to P-G */
/* s[0] = (Py^2 + Gy^2 - 2 Py Gy)/(Px - Gx)^2 - Px - Gx - 486662 */
/* s[1] = (Py^2 + Gy^2 + 2 Py Gy)/(Px - Gx)^2 - Px - Gx - 486662 */
Curve25519.x_to_y2(t1[0], t2[0], p[1]); /* t2[0] = Py^2 */
Curve25519.sqrt(t1[0], t2[0]); /* t1[0] = Py or -Py */
j = Curve25519.is_negative(t1[0]); /* ... check which */
Curve25519.add(t2[0], t2[0], Curve25519.C39420360); /* t2[0] = Py^2 + Gy^2 */
Curve25519.mul(t2[1], Curve25519.BASE_2Y, t1[0]); /* t2[1] = 2 Py Gy or -2 Py Gy */
Curve25519.sub(t1[j], t2[0], t2[1]); /* t1[0] = Py^2 + Gy^2 - 2 Py Gy */
Curve25519.add(t1[1 - j], t2[0], t2[1]); /* t1[1] = Py^2 + Gy^2 + 2 Py Gy */
Curve25519.cpy(t2[0], p[1]); /* t2[0] = Px */
Curve25519.sub(t2[0], t2[0], Curve25519.C9); /* t2[0] = Px - Gx */
Curve25519.sqr(t2[1], t2[0]); /* t2[1] = (Px - Gx)^2 */
Curve25519.recip(t2[0], t2[1], 0); /* t2[0] = 1/(Px - Gx)^2 */
Curve25519.mul(s[0], t1[0], t2[0]); /* s[0] = t1[0]/(Px - Gx)^2 */
Curve25519.sub(s[0], s[0], p[1]); /* s[0] = t1[0]/(Px - Gx)^2 - Px */
Curve25519.sub(s[0], s[0], Curve25519.C486671); /* s[0] = X(P+G) */
Curve25519.mul(s[1], t1[1], t2[0]); /* s[1] = t1[1]/(Px - Gx)^2 */
Curve25519.sub(s[1], s[1], p[1]); /* s[1] = t1[1]/(Px - Gx)^2 - Px */
Curve25519.sub(s[1], s[1], Curve25519.C486671); /* s[1] = X(P-G) */
Curve25519.mul_small(s[0], s[0], 1); /* reduce s[0] */
Curve25519.mul_small(s[1], s[1], 1); /* reduce s[1] */
/* prepare the chain */
for (i = 0; i < 32; i++) {
vi = (vi >> 8) ^ (v[i] & 0xFF) ^ ((v[i] & 0xFF) << 1);
hi = (hi >> 8) ^ (h[i] & 0xFF) ^ ((h[i] & 0xFF) << 1);
nvh = ~(vi ^ hi);
di = (nvh & (di & 0x80) >> 7) ^ vi;
di ^= nvh & (di & 0x01) << 1;
di ^= nvh & (di & 0x02) << 1;
di ^= nvh & (di & 0x04) << 1;
di ^= nvh & (di & 0x08) << 1;
di ^= nvh & (di & 0x10) << 1;
di ^= nvh & (di & 0x20) << 1;
di ^= nvh & (di & 0x40) << 1;
d[i] = di & 0xFF;
}
di = ((nvh & (di & 0x80) << 1) ^ vi) >> 8;
/* initialize state */
Curve25519.set(yx[0], 1);
Curve25519.cpy(yx[1], p[di]);
Curve25519.cpy(yx[2], s[0]);
Curve25519.set(yz[0], 0);
Curve25519.set(yz[1], 1);
Curve25519.set(yz[2], 1);
/* y[0] is (even)P + (even)G
* y[1] is (even)P + (odd)G if current d-bit is 0
* y[1] is (odd)P + (even)G if current d-bit is 1
* y[2] is (odd)P + (odd)G
*/
vi = 0;
hi = 0;
/* and go for it! */
for (i = 32; i-- !== 0;) {
vi = (vi << 8) | (v[i] & 0xFF);
hi = (hi << 8) | (h[i] & 0xFF);
di = (di << 8) | (d[i] & 0xFF);
for (j = 8; j-- !== 0;) {
Curve25519.mont_prep(t1[0], t2[0], yx[0], yz[0]);
Curve25519.mont_prep(t1[1], t2[1], yx[1], yz[1]);
Curve25519.mont_prep(t1[2], t2[2], yx[2], yz[2]);
k = ((vi ^ vi >> 1) >> j & 1)
+ ((hi ^ hi >> 1) >> j & 1);
Curve25519.mont_dbl(yx[2], yz[2], t1[k], t2[k], yx[0], yz[0]);
k = (di >> j & 2) ^ ((di >> j & 1) << 1);
Curve25519.mont_add(t1[1], t2[1], t1[k], t2[k], yx[1], yz[1],
p[di >> j & 1]);
Curve25519.mont_add(t1[2], t2[2], t1[0], t2[0], yx[2], yz[2],
s[((vi ^ hi) >> j & 2) >> 1]);
}
}
k = (vi & 1) + (hi & 1);
Curve25519.recip(t1[0], yz[k], 0);
Curve25519.mul(t1[1], yx[k], t1[0]);
let Y = [];
Curve25519.pack(t1[1], Y);
return Y;
}

Bis Zeile 50. /* prepare the chain */ bin ich durch... nur dann fallen mir die unterschiedlichen Arrays auf die Füße. Denn in der VB/C#-Variante wird alles mit 10 Long-Arrays gelöst und hier eben alles mit UInt16Arrays. Hat von euch jmd vllt. eine Idee wie ich dieses Problem lösen kann? Vllt. einen Arrays-Converter oder so?

Hier noch der VB-Code:

Spoiler anzeigen

Quellcode

Public Shared Function verify(ByVal v As Byte(), ByVal h As Byte(), ByVal pk As Byte()) As Byte()
'/* Y = v abs(P) + h G */
Dim Input_vStr As String = ByteAry2HEX(v) 'v = bed2c0bd00f2e5002c7376632361a55b2ae6a1796d21a64741a9c020b8d95404
Dim Input_hStr As String = ByteAry2HEX(h) 'h = 200fb965e1230bec6a9dc576d1bfa2875c3a6521fa9ced997f79ac608da939f6
Dim Input_pkStr As String = ByteAry2HEX(pk) 'pk = bdb5594cce5dcadb6a4c3af20384a7ad3b8ce045b66535bf0188fdfe7a3b6479
Dim d(31) As Byte
Dim p() As RefCurve25519.Long10 = {New RefCurve25519.Long10, New RefCurve25519.Long10}
Dim s = {New RefCurve25519.Long10, New RefCurve25519.Long10}
Dim yx = {New RefCurve25519.Long10, New RefCurve25519.Long10, New RefCurve25519.Long10}
Dim yz = {New RefCurve25519.Long10, New RefCurve25519.Long10, New RefCurve25519.Long10}
Dim t1 = {New RefCurve25519.Long10, New RefCurve25519.Long10, New RefCurve25519.Long10}
Dim t2 = {New RefCurve25519.Long10, New RefCurve25519.Long10, New RefCurve25519.Long10}
Dim vi = 0, hi = 0, di = 0, nvh = 0, jj, k As Integer
Dim TempPack(31) As Byte
Dim TempPackStr As String = ""
'/* set p[0] to G And p[1] to P */
RefCurve25519.Set(p(0), 9)
RefCurve25519.Unpack(p(1), pk)
'/* set s[0] to P+G And s[1] to P-G */
'/* s[0] = (Py^2 + Gy^2 - 2 Py Gy)/(Px - Gx)^2 - Px - Gx - 486662 */
'/* s[1] = (Py^2 + Gy^2 + 2 Py Gy)/(Px - Gx)^2 - Px - Gx - 486662 */
RefCurve25519.CurveEquationInline(t2(0), p(1), t1(0)) '/* t2[0] = Py ^ 2 */
'#debug#
RefCurve25519.Pack(p(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't1(0) = 78d91ac1f1ae1a9e4200a42ac4a9001fa24b44be8e2b58cd123843684b90235f
' t2(0) = e34bdb568e732b26e4d8400e4c428751868406323388e0228cb7f8b309ddcd43
' p(1) = bdb5594cce5dcadb6a4c3af20384a7ad3b8ce045b66535bf0188fdfe7a3b6479
RefCurve25519.sqrt(t1(0), t2(0)) '/* t1[0] = Py Or -Py */
'#debug#
RefCurve25519.Pack(t1(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't1(0) = "3e88da5e05657c0d44b02f88e89bc1d5914c2d597d2832e3dcc1c3e6291ca727"
jj = RefCurve25519.IsNegative(t1(0)) '/* ... check which */
RefCurve25519.Add(t2(0), t2(0), New RefCurve25519.Long10(RefCurve25519.C39420360, 0, 0, 0, 0, 0, 0, 0, 0, 0)) '/* t2[0] = Py ^ 2 + Gy ^ 2 */
'#debug#
RefCurve25519.Pack(t2(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't2(0) = abcd34598e732b26e4d8400e4c428751868406323388e0228cb7f8b309ddcd43
'3b586202bb742cac9b3c0725036585db665d6e11a745c23f96f2be8ebccca33e
'Dim test As Byte() = HEXStr2ByteAry("3b586202bb742cac9b3c0725036585db665d6e11a745c23f96f2be8ebccca33e")
'Dim test2 As RefCurve25519.Long10 = New RefCurve25519.Long10
'RefCurve25519.Unpack(test2, test)
RefCurve25519.Multiply(t2(1), RefCurve25519.Base2Y, t1(0)) '/* t2[1] = 2 Py Gy Or -2 Py Gy */
'#debug#
RefCurve25519.Pack(t2(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't2(1) = "2823ace230af25bebb3175a816310c9bb0f1f387f808cc20e719b6c8ca0a7d17"
RefCurve25519.Sub(t1(jj), t2(0), t2(1)) '/* t1[0] = Py ^ 2 + Gy ^ 2 - 2 Py Gy */
'#debug#
RefCurve25519.Pack(t1(jj), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't1(jj = 0) = "83aa88765dc4056828a7cb6535117bb6d59212aa3a7f1402a59d42eb3ed2502c"
' t2(0) = "abcd34598e732b26e4d8400e4c428751868406323388e0228cb7f8b309ddcd43"
' t2(1) = "2823ace230af25bebb3175a816310c9bb0f1f387f808cc20e719b6c8ca0a7d17"
'Dim test1 As Byte() = HEXStr2ByteAry("0000000000000000000000000000000000000000000000000000000000000000")
'Dim test1a As RefCurve25519.Long10 = New RefCurve25519.Long10
'RefCurve25519.Unpack(test1a, test1)
'Dim test2 As Byte() = HEXStr2ByteAry("70aa88765dc4056828a7cb6535117bb6d59212aa3a7f1402a59d42eb3ed250ac")
'Dim test2a As RefCurve25519.Long10 = New RefCurve25519.Long10
'RefCurve25519.Unpack(test2a, test2)
'Dim test3 As Byte() = HEXStr2ByteAry("83aa88765dc4056828a7cb6535117bb6d59212aa3a7f1402a59d42eb3ed2502c")
'Dim test3a As RefCurve25519.Long10 = New RefCurve25519.Long10
'RefCurve25519.Unpack(test3a, test3)
'Dim testresult As RefCurve25519.Long10 = New RefCurve25519.Long10
'RefCurve25519.Sub(testresult, test3a, test2a) 'test1a + test2a = (same as ec-kcdsa.js) = 2e78bdcfeb37318e0c800c74815302085c1719dc6d07f52431553b9f48af1e70
'' test1a + test3a = test2a = abcd34598e732b26e4d8400e4c428751868406323388e0228cb7f8b309ddcd43
'' test3a - test2a = (same as ec-kcdsa.js) = 6a557789a23bfa97d758349acaee84492a6ded55c580ebfd5a62bd14c12daf53
'' test2a - test3a = ? = 83aa88765dc4056828a7cb6535117bb6d59212aa3a7f1402a59d42eb3ed2502c
'RefCurve25519.Pack(testresult, TempPack)
'TempPackStr = ByteAry2HEX(TempPack)
RefCurve25519.Add(t1(1 - jj), t2(0), t2(1)) '/* t1[1] = Py ^ 2 + Gy ^ 2 + 2 Py Gy */
'#debug#
RefCurve25519.Pack(t1(1 - jj), TempPack)
TempPackStr = ByteAry2HEX(TempPack) '"d3f0e03bbf2251e49f0ab6b6627393ec3676fab92b91ac4373d1ae7cd4e74a5b"
RefCurve25519.Copy(t2(0), p(1)) '/* t2[0] = Px */
'#debug#
RefCurve25519.Pack(t2(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't2(0) = "bdb5594cce5dcadb6a4c3af20384a7ad3b8ce045b66535bf0188fdfe7a3b6479"
RefCurve25519.Sub(t2(0), t2(0), New RefCurve25519.Long10(9, 0, 0, 0, 0, 0, 0, 0, 0, 0)) '/* t2[0] = Px - Gx */
'#debug#
RefCurve25519.Pack(t2(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't2(0) = "b4b5594cce5dcadb6a4c3af20384a7ad3b8ce045b66535bf0188fdfe7a3b6479"
RefCurve25519.Square(t2(1), t2(0)) '/* t2[1] = (Px - Gx) ^ 2 */
'#debug#
RefCurve25519.Pack(t2(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 't2(1) = 2d879f6da4f68c482054b78baafbfae784fddfbf931d0c5c097f89d542a50d30
RefCurve25519.Reciprocal(t2(0), t2(1), 0) '/* t2[0] = 1/(Px - Gx)^2 */
'#debug#
RefCurve25519.Pack(t2(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) ' t2(0) = cc0db7db039091eeeb2147167228f62106a0bd3a913dd67d93d676537d609b37
RefCurve25519.Multiply(s(0), t1(0), t2(0)) '/* s[0] = t1[0]/(Px - Gx)^2 */
'#debug#
RefCurve25519.Pack(s(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(0) = ad4ad72c0f2e272c5c30dc9aa22f927b654cc5105cf42a385f83e5257031ff13
RefCurve25519.Sub(s(0), s(0), p(1)) '/* s[0] = t1[0]/(Px - Gx)^2 - Px */
'#debug#
RefCurve25519.Pack(s(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(0) = dd947de040d05c50f1e3a1a89eabeacd29c0e4caa58ef5785dfbe726f5f59a1a
RefCurve25519.Sub(s(0), s(0), New RefCurve25519.Long10(RefCurve25519.C486671, 0, 0, 0, 0, 0, 0, 0, 0, 0)) '/* s[0] = X(P + G) */
'#debug#
RefCurve25519.Pack(s(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) ' s(0) = ce2776e040d05c50f1e3a1a89eabeacd29c0e4caa58ef5785dfbe726f5f59a1a
RefCurve25519.Multiply(s(1), t1(1), t2(0)) '/* s[1] = t1[1]/(Px - Gx)^2 */
'#debug#
RefCurve25519.Pack(s(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(1) = c687944436aed57827e1842031e8c99b282beaa0810d21715e8e673c051bde5a
RefCurve25519.Sub(s(1), s(1), p(1)) '/* s[1] = t1[1]/(Px - Gx)^2 - Px */
'#debug#
RefCurve25519.Pack(s(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(1) = f6d13af867500b9dbc944a2e2d6422eeec9e095bcba7ebb15c066a3d8adf7961
RefCurve25519.Sub(s(1), s(1), New RefCurve25519.Long10(RefCurve25519.C486671, 0, 0, 0, 0, 0, 0, 0, 0, 0)) '/* s[1] = X(P - G) */
'#debug#
RefCurve25519.Pack(s(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(1) = e76433f867500b9dbc944a2e2d6422eeec9e095bcba7ebb15c066a3d8adf7961
RefCurve25519.MulSmall(s(0), s(0), 1) '/* reduce s[0] */
'#debug#
RefCurve25519.Pack(s(0), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(0) = ce2776e040d05c50f1e3a1a89eabeacd29c0e4caa58ef5785dfbe726f5f59a1a
RefCurve25519.MulSmall(s(1), s(1), 1) '/* reduce s[1] */
'#debug#
RefCurve25519.Pack(s(1), TempPack)
TempPackStr = ByteAry2HEX(TempPack) 's(1) = e76433f867500b9dbc944a2e2d6422eeec9e095bcba7ebb15c066a3d8adf7961
#Region "Tracestop 1"
'p(0) =
'N0 9 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
'p(1) =
'N0 5879229 Long
'N1 9925523 Long
'N2 26041209 Long
'N3 2068946 Long
'N4 45522448 Long
'N5 31493179 Long
'N6 45275938 Long
'N7 16791526 Long
'N8 61861848 Long
'N9 31822061 Long
's(0) =
'N0 27192331 Long
'N1 24318579 Long
'N2 17573660 Long
'N3 19711439 Long
'N4 5413017 Long
'N5 30672297 Long
'N6 15276307 Long
'N7 12279728 Long
'N8 5320169 Long
'N9 29115157 Long
's(1) =
'N0 41529697 Long
'N1 11249298 Long
'N2 3399453 Long
'N3 34898 Long
'N4 29919506 Long
'N5 19270466 Long
'N6 25013351 Long
'N7 17315350 Long
'N8 935140 Long
'N9 18909289 Long
't1(0) =
'N0 97122056 Long
'N1 19501385 Long
'N2 97391928 Long
'N3 9915679 Long
'N4 45240380 Long
'N5 29422681 Long
'N6 9838121 Long
'N7 46452542 Long
'N8 39555765 Long
'N9 35130938 Long
't1(1) =
'N0 -1203122 Long
'N1 9452179 Long
'N2 7009362 Long
'N3 2725613 Long
'N4 -2496042 Long
'N5 -28568397 Long
'N6 -912119 Long
'N7 -14796422 Long
'N8 -19207071 Long
'N9 417966 Long
't1(2) =
'N0 0 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
't2(0)=
'N0 62328268 Long
'N1 6553846 Long
'N2 4029906 Long
'N3 26260025 Long
'N4 8902817 Long
'N5 12427270 Long
'N6 52349085 Long
'N7 13791162 Long
'N8 64305005 Long
'N9 14577025 Long
't2(1) =
'N0 27232045 Long
'N1 20818203 Long
'N2 42207505 Long
'N3 22306234 Long
'N4 60812270 Long
'N5 31456644 Long
'N6 34523615 Long
'N7 31533953 Long
'N8 2971799 Long
'N9 12596885 Long
't2(2) =
'N0 0 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
#End Region
'/* prepare the chain */
For i As Integer = 0 To 31
vi = (vi >> 8) Xor (v(i) And &HFF) Xor ((v(i) And &HFF) << 1)
hi = (hi >> 8) Xor (h(i) And &HFF) Xor ((h(i) And &HFF) << 1)
nvh = Not (vi Xor hi)
di = (nvh And (di And &H80) >> 7) Xor vi
di = di Xor nvh And (di And &H1) << 1
di = di Xor nvh And (di And &H2) << 1
di = di Xor nvh And (di And &H4) << 1
di = di Xor nvh And (di And &H8) << 1
di = di Xor nvh And (di And &H10) << 1
di = di Xor nvh And (di And &H20) << 1
di = di Xor nvh And (di And &H40) << 1
d(i) = di And &HFF
Next
di = ((nvh And (di And &H80) << 1) Xor vi) >> 8
#Region "Tracestop 2"
'd = deee40420112ea03549db9642dbf5a645a3a629ef562ea597f79435f4826b505
'hi = 282
'vi = 12
'di = 0
#End Region
'/* initialize state */
RefCurve25519.Set(yx(0), 1)
RefCurve25519.Copy(yx(1), p(di))
RefCurve25519.Copy(yx(2), s(0))
RefCurve25519.Set(yz(0), 0)
RefCurve25519.Set(yz(1), 1)
RefCurve25519.Set(yz(2), 1)
#Region "Tracestop 3"
'yx(0) =
'N0 1 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
'yx(1) =
'N0 9 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
'yx(2) =
'N0 27192331 Long
'N1 24318579 Long
'N2 17573660 Long
'N3 19711439 Long
'N4 5413017 Long
'N5 30672297 Long
'N6 15276307 Long
'N7 12279728 Long
'N8 5320169 Long
'N9 29115157 Long
'yz(0) =
'N0 0 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
'yz(1) =
'N0 1 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
'yz(2) =
'N0 1 Long
'N1 0 Long
'N2 0 Long
'N3 0 Long
'N4 0 Long
'N5 0 Long
'N6 0 Long
'N7 0 Long
'N8 0 Long
'N9 0 Long
#End Region
'/* y[0] Is (even)P + (even)G
' * y[1] Is (even)P + (odd)G if current d-bit Is 0
' * y[1] Is (odd)P + (even)G if current d-bit Is 1
' * y[2] Is (odd)P + (odd)G
' */
vi = 0
hi = 0
'And go for it!
For i As Integer = 31 To 0 Step -1
vi = (vi << 8) Or (v(i) And &HFF)
hi = (hi << 8) Or (h(i) And &HFF)
di = (di << 8) Or (d(i) And &HFF)
For j As Integer = 8 To 0 Step -1
RefCurve25519.MontyPrepare(t1(0), t2(0), yx(0), yz(0))
RefCurve25519.MontyPrepare(t1(1), t2(1), yx(1), yz(1))
RefCurve25519.MontyPrepare(t1(2), t2(2), yx(2), yz(2))
k = ((vi Xor vi >> 1) >> j And 1) + ((hi Xor hi >> 1) >> j And 1)
RefCurve25519.MontyDouble(yx(2), yz(2), t1(k), t2(k), yx(0), yz(0))
k = (di >> j And 2) Or ((di >> j And 1) << 1)
RefCurve25519.MontyAdd(t1(1), t2(1), t1(k), t2(k), yx(1), yz(1), p(di >> j And 1))
RefCurve25519.MontyAdd(t1(2), t2(2), t1(0), t2(0), yx(2), yz(2), s(((vi Xor hi) >> j And 2) >> 1))
Next
Next
#Region "Tracestop 4"
'vi = -1111436610 Integer
'hi = 1706626848 Integer
'di = 1111551710 Integer
'k = 2
't1(0) =
'N0 80652174 Long
'N1 52304140 Long
'N2 30594347 Long
'N3 33419878 Long
'N4 58886342 Long
'N5 46170530 Long
'N6 82841748 Long
'N7 40879862 Long
'N8 78485571 Long
'N9 37669871 Long
't1(1) =
'N0 59101306 Long
'N1 14212684 Long
'N2 22378684 Long
'N3 8174658 Long
'N4 18242175 Long
'N5 32162007 Long
'N6 3725737 Long
'N7 6610879 Long
'N8 32011420 Long
'N9 27005631 Long
't1(2) =
'N0 43433296 Long
'N1 28535350 Long
'N2 54616526 Long
'N3 3286957 Long
'N4 44009088 Long
'N5 7814553 Long
'N6 21404851 Long
'N7 29710982 Long
'N8 61374206 Long
'N9 29792398 Long
't2(0) =
'N0 -27974162 Long
'N1 10880740 Long
'N2 29979591 Long
'N3 -522078 Long
'N4 -10540188 Long
'N5 19609484 Long
'N6 18140918 Long
'N7 23191440 Long
'N8 20903125 Long
'N9 17901149 Long
't2(1) =
'N0 30577412 Long
'N1 -8385638 Long
'N2 -23853868 Long
'N3 17400612 Long
'N4 -19780918 Long
'N5 -15733788 Long
'N6 28290292 Long
'N7 -3007844 Long
'N8 -23177790 Long
'N9 -4652416 Long
't2(2) =
'N0 -33490657 Long
'N1 3984873 Long
'N2 11859928 Long
'N3 -4786581 Long
'N4 -6301271 Long
'N5 -10071233 Long
'N6 -27201046 Long
'N7 10991415 Long
'N8 25635918 Long
'N9 -26723488 Long
'yx(0) =
'N0 59150063 Long
'N1 4071334 Long
'N2 13453948 Long
'N3 33019915 Long
'N4 30137134 Long
'N5 23265735 Long
'N6 61416867 Long
'N7 3096186 Long
'N8 60250062 Long
'N9 25932033 Long
'yx(1) =
'N0 39142553 Long
'N1 18963241 Long
'N2 20228824 Long
'N3 14668816 Long
'N4 56781996 Long
'N5 9273275 Long
'N6 24755442 Long
'N7 30808233 Long
'N8 44088001 Long
'N9 23338255 Long
'yx(2) =
'N0 54853063 Long
'N1 10187929 Long
'N2 19951159 Long
'N3 7346679 Long
'N4 62539145 Long
'N5 15066087 Long
'N6 16871919 Long
'N7 22734774 Long
'N8 39982547 Long
'N9 6378161 Long
'yz(0) =
'N0 28785620 Long
'N1 22601994 Long
'N2 23262302 Long
'N3 16422086 Long
'N4 60172685 Long
'N5 32369462 Long
'N6 48153093 Long
'N7 24551075 Long
'N8 55043262 Long
'N9 4839025 Long
'yz(1) =
'N0 62149839 Long
'N1 27250867 Long
'N2 81567 Long
'N3 6463061 Long
'N4 29961849 Long
'N5 21022609 Long
'N6 33531641 Long
'N7 25943479 Long
'N8 19667325 Long
'N9 8169659 Long
'yz(2) =
'N0 45499790 Long
'N1 8293683 Long
'N2 32672976 Long
'N3 26337680 Long
'N4 50195045 Long
'N5 9503606 Long
'N6 25823197 Long
'N7 21171840 Long
'N8 25301773 Long
'N9 20206989 Long
#End Region
k = (vi And 1) + (hi And 1)
'k = 0
RefCurve25519.Reciprocal(t1(0), yz(k), 0)
RefCurve25519.Multiply(t1(1), yx(k), t1(0))
#Region "Tracestop 5"
't1(0) =
'N0 45872088 Long
'N1 33140773 Long
'N2 14911662 Long
'N3 23898813 Long
'N4 62412525 Long
'N5 30064514 Long
'N6 35380908 Long
'N7 14749202 Long
'N8 57081376 Long
'N9 1274365 Long
't1(1) =
'N0 4071327 Long
'N1 27121515 Long
'N2 3684926 Long
'N3 13986023 Long
'N4 63714629 Long
'N5 32417481 Long
'N6 65506912 Long
'N7 22562823 Long
'N8 34259780 Long
'N9 2110758 Long
't1(2) =
'N0 43433296 Long
'N1 28535350 Long
'N2 54616526 Long
'N3 3286957 Long
'N4 44009088 Long
'N5 7814553 Long
'N6 21404851 Long
'N7 29710982 Long
'N8 61374206 Long
'N9 29792398 Long
#End Region
Dim Y(31) As Byte
RefCurve25519.Pack(t1(1), Y)
' Soll = d65c6cc6d1841a3deec249841d7bf1ddeb65625efa70f8d98867a3175a1be526
Dim HEXHEX As String = ByteAry2HEX(Y) 'Y = 0145e6685f5ee3bd65af2821351b2548e7f95fb56d3d368a05c9fc7211481360
Return Y
End Function

Vielen Dank schon mal

exc-jdbi · 31. März 2021, 16:53

Ist von hier und bitte Lizenz durchlesen.
code.google.com/archive/p/curve25519-java/

Hab es kurz übersetzt, finde aber jetzt nicht gerade den Fehler den er hat in der Funktion Test_Equal

Freundliche Grüsse

exc-jdbi

Spoiler anzeigen

Quellcode

Option Strict On
Option Explicit On
Imports System.Threading
Public Module Module1
Public Sub Main()
Dim tk As Double = 0, tv As Double = 0
Console.WriteLine(vbLf & "--- Diffie Hellman (ECDH) ---" & vbLf)
Benchmark("Key agreement", EBench.BENCH_AGREE, 4, 0)
Test_Equal(K, Check1)
Console.WriteLine(" Keypair generation : same" & vbLf)
Console.WriteLine(vbLf & "--- Digital Signatures (EC-KCDSA) ---" & vbLf)
tv = Benchmark("Verification", EBench.BENCH_VERIFY, 4, 0)
Test_Equal(K, Check2)
tk = Benchmark("Keypair generation", EBench.BENCH_KEYGEN, 2, tv)
Test_Equal(E1k, Check3)
Test_Equal(E2k, Check4)
Benchmark("Signing", EBench.BENCH_SIGN, 1, tk + tv)
Test_Equal(K, Check5)
Console.WriteLine(vbLf & "OK")
End Sub
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
Private ReadOnly E1 As Byte() = {3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E2 As Byte() = {5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly K As Byte() = {9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E1k As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E2k As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E1e2k As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E2e1k As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E1s As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private ReadOnly E2s As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Private Sub Xor25519(d As Byte(), s As Byte())
Dim i As Int32
For i = 0 To 32 - 1
d(i) = d(i) Xor s(i)
Next
End Sub
Private Sub Test_Equal(a As Byte(), b As Byte())
Dim i As Int32
For i = 0 To 32 - 1
If a(i) <> b(i) Then
Throw New ArgumentException(vbLf & "*** consistency check failed ***" & vbLf)
End If
Next
End Sub
Private Sub State_Update()
Test_Equal(E1e2k, E2e1k)
Xor25519(E1, E2k)
Xor25519(E2, E1k)
Xor25519(K, E1e2k)
End Sub
Private Enum EBench
BENCH_NOP = 0
BENCH_AGREE = 1
BENCH_VERIFY = 2
BENCH_KEYGEN = 3
BENCH_SIGN = 4
End Enum
Private Function Time_Bench(bench As Int32, count As Int32) As Long
Dim sw = Stopwatch.StartNew()
Dim start As Long = sw.ElapsedTicks
While count <> 0
Select Case bench
Case EBench.BENCH_NOP
Call State_Update()
Exit Select
Case EBench.BENCH_AGREE
Curve25519.Curve(E1k, E1, K)
Curve25519.Curve(E2e1k, E2, E1k)
Curve25519.Curve(E2k, E2, K)
Curve25519.Curve(E1e2k, E1, E2k)
Call State_Update()
Exit Select
Case EBench.BENCH_VERIFY
Curve25519.Verify(E1k, E1, Curve25519.ZERO, K)
Curve25519.Verify(E2e1k, E2, Curve25519.ZERO, E1k)
Curve25519.Verify(E2k, E2, Curve25519.ZERO, K)
Curve25519.Verify(E1e2k, E1, Curve25519.ZERO, E2k)
Call State_Update()
Exit Select
Case EBench.BENCH_KEYGEN
Curve25519.KeyGen(E1k, E1s, E1)
Curve25519.KeyGen(E2k, E2s, E2)
Curve25519.Verify(E1e2k, E1s, K, E1k)
Curve25519.Verify(E2e1k, E2s, K, E2k)
Call State_Update()
Exit Select
Case EBench.BENCH_SIGN
Curve25519.KeyGen(E1k, E1, E1)
Curve25519.KeyGen(E1e2k, Nothing, E2)
Curve25519.Sign(E2k, E1e2k, E2, E1)
Curve25519.Verify(E2e1k, E2k, E1e2k, E1k)
Call State_Update()
Exit Select
End Select
count -= 1
End While
Return (sw.ElapsedTicks - start) \ 1000L
End Function
Private Function Benchmark(what As String, bench As Int32, div As Int32, offset As Double) As Double
Dim TRIES As Int32 = 3
Dim COUNT As Int32 = 2000
Dim i As Int32
Dim time As Double, leasttime As Double = 10000000000.0
Console.WriteLine(what)
'System.out.printf(" %-18s : ", what);
i = TRIES
While Math.Max(Interlocked.Decrement(i), i + 1) <> 0
time = Time_Bench(bench, COUNT \ div)
time -= Time_Bench(EBench.BENCH_NOP, COUNT \ div)
time = time / (COUNT * 1000) - offset
If time < leasttime Then leasttime = time
Console.WriteLine(time.ToString())
'System.out.printf("%.3f ", time);
End While
Console.WriteLine("ms")
'System.out.println("ms");
Return leasttime
End Function
Private ReadOnly Check1 As Byte() = {255, 153, 2, 78, 126, 231, 146, 145, 26, 255, 202, 198, 120, 154, 239, 219, 81, 85, 90, 245, 200, 21, 212, 168, 212, 173, 200, 134, 193, 134, 40, 59}
Private ReadOnly Check2 As Byte() = {4, 104, 164, 208, 209, 140, 151, 93, 72, 158, 222, 60, 125, 144, 106, 156, 92, 147, 23, 242, 55, 205, 177, 40, 247, 214, 178, 151, 252, 74, 150, 25}
Private ReadOnly Check3 As Byte() = {102, 104, 149, 19, 117, 243, 84, 43, 51, 192, 17, 93, 58, 3, 64, 149, 11, 231, 126, 17, 36, 194, 137, 145, 86, 189, 235, 42, 147, 13, 202, 36}
Private ReadOnly Check4 As Byte() = {9, 207, 229, 5, 75, 70, 10, 63, 222, 112, 123, 118, 148, 64, 234, 30, 4, 222, 173, 25, 192, 20, 77, 125, 133, 130, 244, 103, 99, 200, 173, 102}
Private ReadOnly Check5 As Byte() = {71, 17, 254, 189, 183, 208, 95, 116, 185, 63, 163, 50, 130, 44, 231, 155, 150, 39, 72, 139, 42, 211, 82, 0, 249, 172, 10, 191, 147, 50, 100, 101}
End Module
' Ported from C to Java by Dmitry Skiba [sahn0], 23/02/08.
' Original: http://cds.xs4all.nl:8081/ecdh/
'
' Generic 64-bit int32 implementation of Curve25519 ECDH
' Written by Matthijs van Duin, 200608242056
' Public domain.
'
' Based on work by Daniel J Bernstein, http://cr.yp.to/ecdh.html
'
Public Class Curve25519
' key size
Public Shared ReadOnly KEY_SIZE As Int32 = 32
' 0
Public Shared ZERO As Byte() = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
' the prime 2^255-19
Public Shared PRIME As Byte() = {237, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 127}
' group order (a prime near 2^252+2^124)
Public Shared ORDER As Byte() = {237, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 249, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}
' ******* KEY AGREEMENT ********
' Private key clamping
' * k [out] your private key for key agreement
' * k [in] 32 random bytes
'
Public Shared Sub Clamp(k As Byte())
k(31) = Convert.ToByte(k(31) And &H7F)
k(31) = Convert.ToByte(k(31) Or &H40)
k(0) = Convert.ToByte(k(0) And &HF8)
End Sub
' Key-pair generation
' * P [out] your public key
' * s [out] your private key for signing
' * k [out] your private key for key agreement
' * k [in] 32 random bytes
' * s may be NULL if you don't care
' *
' * WARNING: if s is not NULL, this function has data-dependent timing
Public Shared Sub KeyGen(P As Byte(), s As Byte(), k As Byte())
Clamp(k)
Core(P, s, k, Nothing)
End Sub
' Key agreement
' * Z [out] shared secret (needs hashing before use)
' * k [in] your private key for key agreement
' * P [in] peer's public key
'
Public Shared Sub Curve(Z As Byte(), k As Byte(), P As Byte())
Core(Z, Nothing, k, P)
End Sub
' ******* DIGITAL SIGNATURES ********
' deterministic EC-KCDSA
' *
' * s is the private key for signing
' * P is the corresponding public key
' * Z is the context data (signer public key or certificate, etc)
' *
' * signing:
' *
' * m = hash(Z, message)
' * x = hash(m, s)
' * keygen25519(Y, NULL, x);
' * r = hash(Y);
' * h = m XOR r
' * sign25519(v, h, x, s);
' *
' * output (v,r) as the signature
' *
' * verification:
' *
' * m = hash(Z, message);
' * h = m XOR r
' * verify25519(Y, v, h, P)
' *
' * confirm r == hash(Y)
' *
' * It would seem to me that it would be simpler to have the signer directly do
' * h = hash(m, Y) and send that to the recipient instead of r, who can verify
' * the signature by checking h == hash(m, Y). If there are any problems with
' * such a scheme, please let me know.
' *
' * Also, EC-KCDSA (like most DS algorithms) picks x random, which is a waste of
' * perfectly good entropy, but does allow Y to be calculated in advance of (or
' * parallel to) hashing the message.
'
' Signature generation primitive, calculates (x-h)s mod q
' * v [out] signature value
' * h [in] signature hash (of message, signature pub key, and context data)
' * x [in] signature private key
' * s [in] private key for signing
' * returns true on success, false on failure (use different x or h)
'
Public Shared Function Sign(v As Byte(), h As Byte(), x As Byte(), s As Byte()) As Boolean
' v = (x - h) s mod q
Dim tmp1 = New Byte(64) {}
Dim tmp2 = New Byte(32) {}
Dim w, i As Int32
For i = 0 To 32 - 1
v(i) = 0
Next
i = Mula_Small(v, x, 0, h, 32, -1)
Mula_Small(v, v, 0, ORDER, 32, (15 - v(31)) \ 16)
Mula32(tmp1, v, s, 32, 1)
DivMod(tmp2, tmp1, 64, ORDER, 32)
w = 0
i = 0
While i < 32
v(i) = tmp1(i)
w = w Or v(i)
'w = w Or CSharpImpl.__Assign(v(i), tmp1(i))
i += 1
End While
Return w <> 0
End Function
' Signature verification primitive, calculates Y = vP + hG
' * Y [out] signature public key
' * v [in] signature value
' * h [in] signature hash
' * P [in] public key
'
Public Shared Sub Verify(Yk As Byte(), v As Byte(), h As Byte(), Pk As Byte())
' Y = v abs(P) + h G
Dim d = New Byte(31) {}
Dim p As Long10() = New Long10() {New Long10(), New Long10()}, s As Long10() = New Long10() {New Long10(), New Long10()}, yx As Long10() = New Long10() {New Long10(), New Long10(), New Long10()}, yz As Long10() = New Long10() {New Long10(), New Long10(), New Long10()}, t1 As Long10() = New Long10() {New Long10(), New Long10(), New Long10()}, t2 As Long10() = New Long10() {New Long10(), New Long10(), New Long10()}
Dim i, j, k As Int32, vi As Int32 = 0, hi As Int32 = 0, di As Int32 = 0, nvh As Int32 = 0
' set p[0] to G and p[1] to P
[Set](p(0), 9)
Unpack(p(1), Pk)
' set s[0] to P+G and s[1] to P-G
' s[0] = (Py^2 + Gy^2 - 2 Py Gy)/(Px - Gx)^2 - Px - Gx - 486662
' s[1] = (Py^2 + Gy^2 + 2 Py Gy)/(Px - Gx)^2 - Px - Gx - 486662
X_To_Y2(t1(0), t2(0), p(1)) ' t2[0] = Py^2
Sqrt(t1(0), t2(0)) ' t1[0] = Py or -Py
j = Is_Negative(t1(0)) ' ... check which
t2(0)._0 += 39420360 ' t2[0] = Py^2 + Gy^2
Mul(t2(1), BASE_2Y, t1(0)) ' t2[1] = 2 Py Gy or -2 Py Gy
[Sub](t1(j), t2(0), t2(1)) ' t1[0] = Py^2 + Gy^2 - 2 Py Gy
Add(t1(1 - j), t2(0), t2(1)) ' t1[1] = Py^2 + Gy^2 + 2 Py Gy
Cpy(t2(0), p(1)) ' t2[0] = Px
t2(0)._0 -= 9 ' t2[0] = Px - Gx
Sqr(t2(1), t2(0)) ' t2[1] = (Px - Gx)^2
Recip(t2(0), t2(1), 0) ' t2[0] = 1/(Px - Gx)^2
Mul(s(0), t1(0), t2(0)) ' s[0] = t1[0]/(Px - Gx)^2
[Sub](s(0), s(0), p(1)) ' s[0] = t1[0]/(Px - Gx)^2 - Px
s(0)._0 -= 9 + 486662 ' s[0] = X(P+G)
Mul(s(1), t1(1), t2(0)) ' s[1] = t1[1]/(Px - Gx)^2
[Sub](s(1), s(1), p(1)) ' s[1] = t1[1]/(Px - Gx)^2 - Px
s(1)._0 -= 9 + 486662 ' s[1] = X(P-G)
Mul_Small(s(0), s(0), 1) ' reduce s[0]
Mul_Small(s(1), s(1), 1) ' reduce s[1]
' prepare the chain
For i = 0 To 32 - 1
vi = vi >> 8 Xor v(i) And &HFF Xor (v(i) And &HFF) << 1
hi = hi >> 8 Xor h(i) And &HFF Xor (h(i) And &HFF) << 1
nvh = Not (vi Xor hi)
di = nvh And (di And &H80) >> 7 Xor vi
di = di Xor nvh And (di And &H1) << 1
di = di Xor nvh And (di And &H2) << 1
di = di Xor nvh And (di And &H4) << 1
di = di Xor nvh And (di And &H8) << 1
di = di Xor nvh And (di And &H10) << 1
di = di Xor nvh And (di And &H20) << 1
di = di Xor nvh And (di And &H40) << 1
d(i) = Convert.ToByte(di And &HFF)
Next
di = (nvh And (di And &H80) << 1 Xor vi) >> 8
' initialize state
[Set](yx(0), 1)
Cpy(yx(1), p(di))
Cpy(yx(2), s(0))
[Set](yz(0), 0)
[Set](yz(1), 1)
[Set](yz(2), 1)
' y[0] is (even)P + (even)G
' * y[1] is (even)P + (odd)G if current d-bit is 0
' * y[1] is (odd)P + (even)G if current d-bit is 1
' * y[2] is (odd)P + (odd)G
'
vi = 0
hi = 0
' and go for it!
i = 32
While Math.Max(Interlocked.Decrement(i), i + 1) <> 0
vi = vi << 8 Or v(i) And &HFF
hi = hi << 8 Or h(i) And &HFF
di = di << 8 Or d(i) And &HFF
j = 8
While Math.Max(Interlocked.Decrement(j), j + 1) <> 0
Mont_Prep(t1(0), t2(0), yx(0), yz(0))
Mont_Prep(t1(1), t2(1), yx(1), yz(1))
Mont_Prep(t1(2), t2(2), yx(2), yz(2))
k = ((vi Xor vi >> 1) >> j And 1) + ((hi Xor hi >> 1) >> j And 1)
Mont_Dbl(yx(2), yz(2), t1(k), t2(k), yx(0), yz(0))
k = di >> j And 2 Xor (di >> j And 1) << 1
Mont_Add(t1(1), t2(1), t1(k), t2(k), yx(1), yz(1), p(di >> j And 1))
Mont_Add(t1(2), t2(2), t1(0), t2(0), yx(2), yz(2), s(((vi Xor hi) >> j And 2) >> 1))
End While
End While
k = (vi And 1) + (hi And 1)
Recip(t1(0), yz(k), 0)
Mul(t1(1), yx(k), t1(0))
Pack(t1(1), Yk)
End Sub
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
' sahn0:
' * Using this class instead of long[10] to avoid bounds checks.
Private Class Long10
Public Sub New()
End Sub
Public Sub New(_0 As Long, _1 As Long, _2 As Long, _3 As Long, _4 As Long, _5 As Long, _6 As Long, _7 As Long, _8 As Long, _9 As Long)
Me._0 = _0 : Me._1 = _1 : Me._2 = _2 : Me._3 = _3 : Me._4 = _4
Me._5 = _5 : Me._6 = _6 : Me._7 = _7 : Me._8 = _8 : Me._9 = _9
End Sub
Public _0, _1, _2, _3, _4, _5, _6, _7, _8, _9 As Long
End Class
' ******************* radix 2^8 math ********************
Private Shared Sub Cpy32(d As Byte(), s As Byte())
Dim i As Int32
For i = 0 To 32 - 1
d(i) = s(i)
Next
End Sub
' p[m..n+m-1] = q[m..n+m-1] + z * x
' n is the size of x
' n+m is the size of p and q
Private Shared Function Mula_Small(p As Byte(), q As Byte(), m As Int32, x As Byte(), n As Int32, z As Int32) As Int32
Dim v As Int32 = 0, i As Int32 = 0
While i < n
v += (q(i + m) And &HFF) + z * (x(i) And &HFF)
p(i + m) = Convert.ToByte(v And &HFF)
v >>= 8
i += 1
End While
Return v
End Function
' p += x * y * z where z is a small int32
' * x is size 32, y is size t, p is size 32+t
' * y is allowed to overlap with p+32 if you don't care about the upper half
Private Shared Function Mula32(p As Byte(), x As Byte(), y As Byte(), t As Int32, z As Int32) As Int32
Dim n As Int32 = 31
Dim w As Int32 = 0
Dim i As Int32 = 0
While i < t
Dim zy As Int32 = z * (y(i) And &HFF)
w += Mula_Small(p, p, i, x, n, zy) + (p(i + n) And &HFF) + zy * (x(n) And &HFF)
p(i + n) = Convert.ToByte(w And &HFF)
w >>= 8
i += 1
End While
p(i + n) = Convert.ToByte((w + (p(i + n) And &HFF)) And &HFF)
Return w >> 8
End Function
' divide r (size n) by d (size t), returning quotient q and remainder r
' * quotient is size n-t+1, remainder is size t
' * requires t > 0 && d[t-1] != 0
' * requires that r[-1] and d[-1] are valid memory locations
' * q may overlap with r+t
Private Shared Sub DivMod(q As Byte(), r As Byte(), n As Int32, d As Byte(), t As Int32)
Dim rn As Int32 = 0
Dim dt As Int32 = (d(t - 1) And &HFF) << 8
If t > 1 Then
dt = dt Or d(t - 2) And &HFF
End If
While Math.Max(Interlocked.Decrement(n), n + 1) >= t
Dim z As Int32 = rn << 16 Or (r(n) And &HFF) << 8
If n > 0 Then
z = z Or r(n - 1) And &HFF
End If
z \= dt
rn += Mula_Small(r, r, n - t + 1, d, t, -z)
q(n - t + 1) = Convert.ToByte(z + rn And &HFF) ' rn is 0 or -1 (underflow)
Mula_Small(r, r, n - t + 1, d, t, -rn)
rn = r(n) And &HFF
r(n) = 0
End While
r(t - 1) = Convert.ToByte(rn)
End Sub
Private Shared Function NumSize(x As Byte(), n As Int32) As Int32
While Math.Max(Interlocked.Decrement(n), n + 1) <> 0 AndAlso x(n) = 0
End While
Return n + 1
End Function
' Returns x if a contains the gcd, y if b.
' * Also, the returned buffer contains the inverse of a mod b,
' * as 32-byte signed.
' * x and y must have 64 bytes space for temporary use.
' * requires that a[-1] and b[-1] are valid memory locations
Private Shared Function Egcd32(x As Byte(), y As Byte(), a As Byte(), b As Byte()) As Byte()
Dim an, qn, i As Int32, bn As Int32 = 32
For i = 0 To 32 - 1
y(i) = 0 : x(i) = 0
Next
x(0) = 1
an = NumSize(a, 32)
If an = 0 Then Return y ' division by zero
Dim temp As Byte() = New Byte(31) {}
While True
qn = bn - an + 1
DivMod(temp, b, bn, a, an)
bn = NumSize(b, bn)
If bn = 0 Then Return x
Mula32(y, x, temp, qn, -1)
qn = an - bn + 1
DivMod(temp, a, an, b, bn)
an = NumSize(a, an)
If an = 0 Then Return y
Mula32(x, y, temp, qn, -1)
End While
Throw New Exception()
End Function
' ******************* radix 2^25.5 GF(2^255-19) math ********************
Private Shared ReadOnly P25 As Int32 = 33554431 ' (1 << 25) - 1
Private Shared ReadOnly P26 As Int32 = 67108863 ' (1 << 26) - 1
' Convert to internal format from little-endian byte format
Private Shared Sub Unpack(x As Long10, m As Byte())
x._0 = m(0) And &HFF Or (m(1) And &HFF) << 8 Or (m(2) And &HFF) << 16 Or (m(3) And &HFF And 3) << 24
x._1 = (m(3) And &HFF And Not 3) >> 2 Or (m(4) And &HFF) << 6 Or (m(5) And &HFF) << 14 Or (m(6) And &HFF And 7) << 22
x._2 = (m(6) And &HFF And Not 7) >> 3 Or (m(7) And &HFF) << 5 Or (m(8) And &HFF) << 13 Or (m(9) And &HFF And 31) << 21
x._3 = (m(9) And &HFF And Not 31) >> 5 Or (m(10) And &HFF) << 3 Or (m(11) And &HFF) << 11 Or (m(12) And &HFF And 63) << 19
x._4 = (m(12) And &HFF And Not 63) >> 6 Or (m(13) And &HFF) << 2 Or (m(14) And &HFF) << 10 Or (m(15) And &HFF) << 18
x._5 = m(16) And &HFF Or (m(17) And &HFF) << 8 Or (m(18) And &HFF) << 16 Or (m(19) And &HFF And 1) << 24
x._6 = (m(19) And &HFF And Not 1) >> 1 Or (m(20) And &HFF) << 7 Or (m(21) And &HFF) << 15 Or (m(22) And &HFF And 7) << 23
x._7 = (m(22) And &HFF And Not 7) >> 3 Or (m(23) And &HFF) << 5 Or (m(24) And &HFF) << 13 Or (m(25) And &HFF And 15) << 21
x._8 = (m(25) And &HFF And Not 15) >> 4 Or (m(26) And &HFF) << 4 Or (m(27) And &HFF) << 12 Or (m(28) And &HFF And 63) << 20
x._9 = (m(28) And &HFF And Not 63) >> 6 Or (m(29) And &HFF) << 2 Or (m(30) And &HFF) << 10 Or (m(31) And &HFF) << 18
End Sub
' Check if reduced-form input >= 2^255-19
Private Shared Function Is_Overflow(x As Long10) As Boolean
Return x._0 > P26 - 19 AndAlso (x._1 And x._3 And x._5 And x._7 And x._9) = P25 AndAlso (x._2 And x._4 And x._6 And x._8) = P26 OrElse x._9 > P25
End Function
' Convert from internal format to little-endian byte format. The
' * number must be in a reduced form which is output by the following ops:
' * unpack, mul, sqr
' * set -- if input in range 0 .. P25
' * If you're unsure if the number is reduced, first multiply it by 1.
Private Shared Sub Pack(x As Long10, m As Byte())
Dim ld As Int32 = 0, ud As Int32 = 0
Dim t As Long
ld = If(Is_Overflow(x), 1, 0) - If(x._9 < 0, 1, 0)
ud = ld * -(P25 + 1)
ld *= 19
t = ld + x._0 + (x._1 << 26)
m(0) = Convert.ToByte(t And &HFF)
m(1) = Convert.ToByte((t >> 8) And &HFF)
m(2) = Convert.ToByte((t >> 16) And &HFF)
m(3) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + (x._2 << 19)
m(4) = Convert.ToByte(t And &HFF)
m(5) = Convert.ToByte((t >> 8) And &HFF)
m(6) = Convert.ToByte((t >> 16) And &HFF)
m(7) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + (x._3 << 13)
m(8) = Convert.ToByte(t And &HFF)
m(9) = Convert.ToByte((t >> 8) And &HFF)
m(10) = Convert.ToByte((t >> 16) And &HFF)
m(11) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + (x._4 << 6)
m(12) = Convert.ToByte(t And &HFF)
m(13) = Convert.ToByte((t >> 8) And &HFF)
m(14) = Convert.ToByte((t >> 16) And &HFF)
m(15) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + x._5 + (x._6 << 25)
m(16) = Convert.ToByte(t And &HFF)
m(17) = Convert.ToByte((t >> 8) And &HFF)
m(18) = Convert.ToByte((t >> 16) And &HFF)
m(19) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + (x._7 << 19)
m(20) = Convert.ToByte(t And &HFF)
m(21) = Convert.ToByte((t >> 8) And &HFF)
m(22) = Convert.ToByte((t >> 16) And &HFF)
m(23) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + (x._8 << 12)
m(24) = Convert.ToByte(t And &HFF)
m(25) = Convert.ToByte((t >> 8) And &HFF)
m(26) = Convert.ToByte((t >> 16) And &HFF)
m(27) = Convert.ToByte((t >> 24) And &HFF)
t = (t >> 32) + (x._9 + ud << 6)
m(28) = Convert.ToByte(t And &HFF)
m(29) = Convert.ToByte((t >> 8) And &HFF)
m(30) = Convert.ToByte((t >> 16) And &HFF)
m(31) = Convert.ToByte((t >> 24) And &HFF)
End Sub
' Copy a number
Private Shared Sub Cpy(_out As Long10, _in As Long10)
_out._0 = _in._0
_out._1 = _in._1
_out._2 = _in._2
_out._3 = _in._3
_out._4 = _in._4
_out._5 = _in._5
_out._6 = _in._6
_out._7 = _in._7
_out._8 = _in._8
_out._9 = _in._9
End Sub
' Set a number to value, which must be in range -185861411 .. 185861411
Private Shared Sub [Set](_out As Long10, _in As Int32)
_out._0 = _in
_out._1 = 0
_out._2 = 0
_out._3 = 0
_out._4 = 0
_out._5 = 0
_out._6 = 0
_out._7 = 0
_out._8 = 0
_out._9 = 0
End Sub
' Add/subtract two numbers. The inputs must be in reduced form, and the
' * output isn't, so to do another addition or subtraction on the output,
' * first multiply it by one to reduce it.
Private Shared Sub Add(xy As Long10, x As Long10, y As Long10)
xy._0 = x._0 + y._0
xy._1 = x._1 + y._1
xy._2 = x._2 + y._2
xy._3 = x._3 + y._3
xy._4 = x._4 + y._4
xy._5 = x._5 + y._5
xy._6 = x._6 + y._6
xy._7 = x._7 + y._7
xy._8 = x._8 + y._8
xy._9 = x._9 + y._9
End Sub
Private Shared Sub [Sub](xy As Long10, x As Long10, y As Long10)
xy._0 = x._0 - y._0
xy._1 = x._1 - y._1
xy._2 = x._2 - y._2
xy._3 = x._3 - y._3
xy._4 = x._4 - y._4
xy._5 = x._5 - y._5
xy._6 = x._6 - y._6
xy._7 = x._7 - y._7
xy._8 = x._8 - y._8
xy._9 = x._9 - y._9
End Sub
' Multiply a number by a small int32 in range -185861411 .. 185861411.
' * The output is in reduced form, the input x need not be. x and xy may point
' * to the same buffer.
Private Shared Function Mul_Small(xy As Long10, x As Long10, y As Long) As Long10
Dim t As Long
t = x._8 * y
xy._8 = t And (1 << 26) - 1
t = (t >> 26) + x._9 * y
xy._9 = t And (1 << 25) - 1
t = 19 * (t >> 25) + x._0 * y
xy._0 = t And (1 << 26) - 1
t = (t >> 26) + x._1 * y
xy._1 = t And (1 << 25) - 1
t = (t >> 25) + x._2 * y
xy._2 = t And (1 << 26) - 1
t = (t >> 26) + x._3 * y
xy._3 = t And (1 << 25) - 1
t = (t >> 25) + x._4 * y
xy._4 = t And (1 << 26) - 1
t = (t >> 26) + x._5 * y
xy._5 = t And (1 << 25) - 1
t = (t >> 25) + x._6 * y
xy._6 = t And (1 << 26) - 1
t = (t >> 26) + x._7 * y
xy._7 = t And (1 << 25) - 1
t = (t >> 25) + xy._8
xy._8 = t And (1 << 26) - 1
xy._9 += t >> 26
Return xy
End Function
' Multiply two numbers. The output is in reduced form, the inputs need not
' * be.
Private Shared Function Mul(xy As Long10, x As Long10, y As Long10) As Long10
' sahn0:
' * Using local variables to avoid class access.
' * This seem to improve performance a bit...
'
Dim x_0 As Long = x._0, x_1 As Long = x._1, x_2 As Long = x._2, x_3 As Long = x._3, x_4 As Long = x._4, x_5 As Long = x._5, x_6 As Long = x._6, x_7 As Long = x._7, x_8 As Long = x._8, x_9 As Long = x._9
Dim y_0 As Long = y._0, y_1 As Long = y._1, y_2 As Long = y._2, y_3 As Long = y._3, y_4 As Long = y._4, y_5 As Long = y._5, y_6 As Long = y._6, y_7 As Long = y._7, y_8 As Long = y._8, y_9 As Long = y._9
Dim t As Long
t = x_0 * y_8 + x_2 * y_6 + x_4 * y_4 + x_6 * y_2 + x_8 * y_0 + 2 * (x_1 * y_7 + x_3 * y_5 + x_5 * y_3 + x_7 * y_1) + 38 * (x_9 * y_9)
xy._8 = t And (1 << 26) - 1
t = (t >> 26) + x_0 * y_9 + x_1 * y_8 + x_2 * y_7 + x_3 * y_6 + x_4 * y_5 + x_5 * y_4 + x_6 * y_3 + x_7 * y_2 + x_8 * y_1 + x_9 * y_0
xy._9 = t And (1 << 25) - 1
t = x_0 * y_0 + 19 * ((t >> 25) + x_2 * y_8 + x_4 * y_6 + x_6 * y_4 + x_8 * y_2) + 38 * (x_1 * y_9 + x_3 * y_7 + x_5 * y_5 + x_7 * y_3 + x_9 * y_1)
xy._0 = t And (1 << 26) - 1
t = (t >> 26) + x_0 * y_1 + x_1 * y_0 + 19 * (x_2 * y_9 + x_3 * y_8 + x_4 * y_7 + x_5 * y_6 + x_6 * y_5 + x_7 * y_4 + x_8 * y_3 + x_9 * y_2)
xy._1 = t And (1 << 25) - 1
t = (t >> 25) + x_0 * y_2 + x_2 * y_0 + 19 * (x_4 * y_8 + x_6 * y_6 + x_8 * y_4) + 2 * (x_1 * y_1) + 38 * (x_3 * y_9 + x_5 * y_7 + x_7 * y_5 + x_9 * y_3)
xy._2 = t And (1 << 26) - 1
t = (t >> 26) + x_0 * y_3 + x_1 * y_2 + x_2 * y_1 + x_3 * y_0 + 19 * (x_4 * y_9 + x_5 * y_8 + x_6 * y_7 + x_7 * y_6 + x_8 * y_5 + x_9 * y_4)
xy._3 = t And (1 << 25) - 1
t = (t >> 25) + x_0 * y_4 + x_2 * y_2 + x_4 * y_0 + 19 * (x_6 * y_8 + x_8 * y_6) + 2 * (x_1 * y_3 + x_3 * y_1) + 38 * (x_5 * y_9 + x_7 * y_7 + x_9 * y_5)
xy._4 = t And (1 << 26) - 1
t = (t >> 26) + x_0 * y_5 + x_1 * y_4 + x_2 * y_3 + x_3 * y_2 + x_4 * y_1 + x_5 * y_0 + 19 * (x_6 * y_9 + x_7 * y_8 + x_8 * y_7 + x_9 * y_6)
xy._5 = t And (1 << 25) - 1
t = (t >> 25) + x_0 * y_6 + x_2 * y_4 + x_4 * y_2 + x_6 * y_0 + 19 * (x_8 * y_8) + 2 * (x_1 * y_5 + x_3 * y_3 + x_5 * y_1) + 38 * (x_7 * y_9 + x_9 * y_7)
xy._6 = t And (1 << 26) - 1
t = (t >> 26) + x_0 * y_7 + x_1 * y_6 + x_2 * y_5 + x_3 * y_4 + x_4 * y_3 + x_5 * y_2 + x_6 * y_1 + x_7 * y_0 + 19 * (x_8 * y_9 + x_9 * y_8)
xy._7 = t And (1 << 25) - 1
t = (t >> 25) + xy._8
xy._8 = t And (1 << 26) - 1
xy._9 += t >> 26
Return xy
End Function
' Square a number. Optimization of mul25519(x2, x, x)
Private Shared Function Sqr(x2 As Long10, x As Long10) As Long10
Dim x_0 As Long = x._0, x_1 As Long = x._1, x_2 As Long = x._2, x_3 As Long = x._3, x_4 As Long = x._4, x_5 As Long = x._5, x_6 As Long = x._6, x_7 As Long = x._7, x_8 As Long = x._8, x_9 As Long = x._9
Dim t As Long
t = x_4 * x_4 + 2 * (x_0 * x_8 + x_2 * x_6) + 38 * (x_9 * x_9) + 4 * (x_1 * x_7 + x_3 * x_5)
x2._8 = t And (1 << 26) - 1
t = (t >> 26) + 2 * (x_0 * x_9 + x_1 * x_8 + x_2 * x_7 + x_3 * x_6 + x_4 * x_5)
x2._9 = t And (1 << 25) - 1
t = 19 * (t >> 25) + x_0 * x_0 + 38 * (x_2 * x_8 + x_4 * x_6 + x_5 * x_5) + 76 * (x_1 * x_9 + x_3 * x_7)
x2._0 = t And (1 << 26) - 1
t = (t >> 26) + 2 * (x_0 * x_1) + 38 * (x_2 * x_9 + x_3 * x_8 + x_4 * x_7 + x_5 * x_6)
x2._1 = t And (1 << 25) - 1
t = (t >> 25) + 19 * (x_6 * x_6) + 2 * (x_0 * x_2 + x_1 * x_1) + 38 * (x_4 * x_8) + 76 * (x_3 * x_9 + x_5 * x_7)
x2._2 = t And (1 << 26) - 1
t = (t >> 26) + 2 * (x_0 * x_3 + x_1 * x_2) + 38 * (x_4 * x_9 + x_5 * x_8 + x_6 * x_7)
x2._3 = t And (1 << 25) - 1
t = (t >> 25) + x_2 * x_2 + 2 * (x_0 * x_4) + 38 * (x_6 * x_8 + x_7 * x_7) + 4 * (x_1 * x_3) + 76 * (x_5 * x_9)
x2._4 = t And (1 << 26) - 1
t = (t >> 26) + 2 * (x_0 * x_5 + x_1 * x_4 + x_2 * x_3) + 38 * (x_6 * x_9 + x_7 * x_8)
x2._5 = t And (1 << 25) - 1
t = (t >> 25) + 19 * (x_8 * x_8) + 2 * (x_0 * x_6 + x_2 * x_4 + x_3 * x_3) + 4 * (x_1 * x_5) + 76 * (x_7 * x_9)
x2._6 = t And (1 << 26) - 1
t = (t >> 26) + 2 * (x_0 * x_7 + x_1 * x_6 + x_2 * x_5 + x_3 * x_4) + 38 * (x_8 * x_9)
x2._7 = t And (1 << 25) - 1
t = (t >> 25) + x2._8
x2._8 = t And (1 << 26) - 1
x2._9 += t >> 26
Return x2
End Function
' Calculates a reciprocal. The output is in reduced form, the inputs need not
' * be. Simply calculates y = x^(p-2) so it's not too fast.
' When sqrtassist is true, it instead calculates y = x^((p-5)/8)
Private Shared Sub Recip(y As Long10, x As Long10, sqrtassist As Int32)
Dim t0 As Long10 = New Long10(), t1 As Long10 = New Long10(), t2 As Long10 = New Long10(), t3 As Long10 = New Long10(), t4 As Long10 = New Long10()
Dim i As Int32
' the chain for x^(2^255-21) is straight from djb's implementation
Sqr(t1, x) ' 2 == 2 * 1
Sqr(t2, t1) ' 4 == 2 * 2
Sqr(t0, t2) ' 8 == 2 * 4
Mul(t2, t0, x) ' 9 == 8 + 1
Mul(t0, t2, t1) ' 11 == 9 + 2
Sqr(t1, t0) ' 22 == 2 * 11
Mul(t3, t1, t2) ' 31 == 22 + 9 == 2^5 - 2^0
Sqr(t1, t3) ' 2^6 - 2^1
Sqr(t2, t1) ' 2^7 - 2^2
Sqr(t1, t2) ' 2^8 - 2^3
Sqr(t2, t1) ' 2^9 - 2^4
Sqr(t1, t2) ' 2^10 - 2^5
Mul(t2, t1, t3) ' 2^10 - 2^0
Sqr(t1, t2) ' 2^11 - 2^1
Sqr(t3, t1) ' 2^12 - 2^2
For i = 1 To 5 - 1
Sqr(t1, t3)
Sqr(t3, t1)
Next ' t3
' 2^20 - 2^10
Mul(t1, t3, t2) ' 2^20 - 2^0
Sqr(t3, t1) ' 2^21 - 2^1
Sqr(t4, t3) ' 2^22 - 2^2
For i = 1 To 10 - 1
Sqr(t3, t4)
Sqr(t4, t3)
Next ' t4
' 2^40 - 2^20
Mul(t3, t4, t1) ' 2^40 - 2^0
For i = 0 To 5 - 1
Sqr(t1, t3)
Sqr(t3, t1)
Next ' t3
' 2^50 - 2^10
Mul(t1, t3, t2) ' 2^50 - 2^0
Sqr(t2, t1) ' 2^51 - 2^1
Sqr(t3, t2) ' 2^52 - 2^2
For i = 1 To 25 - 1
Sqr(t2, t3)
Sqr(t3, t2)
Next ' t3
' 2^100 - 2^50
Mul(t2, t3, t1) ' 2^100 - 2^0
Sqr(t3, t2) ' 2^101 - 2^1
Sqr(t4, t3) ' 2^102 - 2^2
For i = 1 To 50 - 1
Sqr(t3, t4)
Sqr(t4, t3)
Next ' t4
' 2^200 - 2^100
Mul(t3, t4, t2) ' 2^200 - 2^0
For i = 0 To 25 - 1
Sqr(t4, t3)
Sqr(t3, t4)
Next ' t3
' 2^250 - 2^50
Mul(t2, t3, t1) ' 2^250 - 2^0
Sqr(t1, t2) ' 2^251 - 2^1
Sqr(t2, t1) ' 2^252 - 2^2
If sqrtassist <> 0 Then
Mul(y, x, t2) ' 2^252 - 3
Else
Sqr(t1, t2) ' 2^253 - 2^3
Sqr(t2, t1) ' 2^254 - 2^4
Sqr(t1, t2) ' 2^255 - 2^5
Mul(y, t1, t0) ' 2^255 - 21
End If
End Sub
' checks if x is "negative", requires reduced input
Private Shared Function Is_Negative(x As Long10) As Int32
Return Convert.ToInt32(If(Is_Overflow(x) OrElse x._9 < 0, 1, 0) Xor (x._0 And 1))
End Function
' a square root
Private Shared Sub Sqrt(x As Long10, u As Long10)
Dim v As Long10 = New Long10(), t1 As Long10 = New Long10(), t2 As Long10 = New Long10()
Add(t1, u, u) ' t1 = 2u
Recip(v, t1, 1) ' v = (2u)^((p-5)/8)
Sqr(x, v) ' x = v^2
Mul(t2, t1, x) ' t2 = 2uv^2
t2._0 -= 1 ' t2 = 2uv^2-1
Mul(t1, v, t2) ' t1 = v(2uv^2-1)
Mul(x, u, t1) ' x = uv(2uv^2-1)
End Sub
' ******************* Elliptic curve ********************
' y^2 = x^3 + 486662 x^2 + x over GF(2^255-19)
' t1 = ax + az
' * t2 = ax - az
Private Shared Sub Mont_Prep(t1 As Long10, t2 As Long10, ax As Long10, az As Long10)
Add(t1, ax, az)
[Sub](t2, ax, az)
End Sub
' A = P + Q where
' * X(A) = ax/az
' * X(P) = (t1+t2)/(t1-t2)
' * X(Q) = (t3+t4)/(t3-t4)
' * X(P-Q) = dx
' * clobbers t1 and t2, preserves t3 and t4
Private Shared Sub Mont_Add(t1 As Long10, t2 As Long10, t3 As Long10, t4 As Long10, ax As Long10, az As Long10, dx As Long10)
Mul(ax, t2, t3)
Mul(az, t1, t4)
Add(t1, ax, az)
[Sub](t2, ax, az)
Sqr(ax, t1)
Sqr(t1, t2)
Mul(az, t1, dx)
End Sub
' B = 2 * Q where
' * X(B) = bx/bz
' * X(Q) = (t3+t4)/(t3-t4)
' * clobbers t1 and t2, preserves t3 and t4
Private Shared Sub Mont_Dbl(t1 As Long10, t2 As Long10, t3 As Long10, t4 As Long10, bx As Long10, bz As Long10)
Sqr(t1, t3)
Sqr(t2, t4)
Mul(bx, t1, t2)
[Sub](t2, t1, t2)
Mul_Small(bz, t2, 121665)
Add(t1, t1, bz)
Mul(bz, t1, t2)
End Sub
' Y^2 = X^3 + 486662 X^2 + X
' * t is a temporary
Private Shared Sub X_To_Y2(t As Long10, y2 As Long10, x As Long10)
Sqr(t, x)
Mul_Small(y2, x, 486662)
Add(t, t, y2)
t._0 += 1
Mul(y2, t, x)
End Sub
' P = kG and s = sign(P)/k
Private Shared Sub Core(Px As Byte(), s As Byte(), k As Byte(), Gx As Byte())
Dim dx As Long10 = New Long10(), t1 As Long10 = New Long10(), t2 As Long10 = New Long10(), t3 As Long10 = New Long10(), t4 As Long10 = New Long10()
Dim x As Long10() = New Long10() {New Long10(), New Long10()}, z As Long10() = New Long10() {New Long10(), New Long10()}
Dim i, j As Int32
' unpack the base
If Gx IsNot Nothing Then
Unpack(dx, Gx)
Else
[Set](dx, 9)
End If
' 0G = point-at-infinity
[Set](x(0), 1)
[Set](z(0), 0)
' 1G = G
Cpy(x(1), dx)
[Set](z(1), 1)
i = 32
While Math.Max(Interlocked.Decrement(i), i + 1) <> 0
If i = 0 Then
i = 0
End If
j = 8
While Math.Max(Interlocked.Decrement(j), j + 1) <> 0
' swap arguments depending on bit
Dim bit1 As Int32 = (k(i) And &HFF) >> j And 1
Dim bit0 As Int32 = Not (k(i) And &HFF) >> j And 1
Dim ax As Long10 = x(bit0)
Dim az As Long10 = z(bit0)
Dim bx As Long10 = x(bit1)
Dim bz As Long10 = z(bit1)
' a' = a + b
' b' = 2 b
Mont_Prep(t1, t2, ax, az)
Mont_Prep(t3, t4, bx, bz)
Mont_Add(t1, t2, t3, t4, ax, az, dx)
Mont_Dbl(t1, t2, t3, t4, bx, bz)
End While
End While
Recip(t1, z(0), 0)
Mul(dx, x(0), t1)
Pack(dx, Px)
' calculate s such that s abs(P) = G .. assumes G is std base point
If s IsNot Nothing Then
X_To_Y2(t2, t1, dx) ' t1 = Py^2
Recip(t3, z(1), 0) ' where Q=P+G ...
Mul(t2, x(1), t3) ' t2 = Qx
Add(t2, t2, dx) ' t2 = Qx + Px
t2._0 += 9 + 486662 ' t2 = Qx + Px + Gx + 486662
dx._0 -= 9 ' dx = Px - Gx
Sqr(t3, dx) ' t3 = (Px - Gx)^2
Mul(dx, t2, t3) ' dx = t2 (Px - Gx)^2
[Sub](dx, dx, t1) ' dx = t2 (Px - Gx)^2 - Py^2
dx._0 -= 39420360 ' dx = t2 (Px - Gx)^2 - Py^2 - Gy^2
Mul(t1, dx, BASE_R2Y) ' t1 = -Py
If Is_Negative(t1) <> 0 Then ' sign is 1, so just copy
Cpy32(s, k) ' sign is -1, so negate
Else
Mula_Small(s, ORDER_TIMES_8, 0, k, 32, -1)
End If
' reduce s mod q
' * (is this needed? do it just in case, it's fast anyway)
'divmod((dstptr) t1, s, 32, order25519, 32);
' take reciprocal of s mod q
Dim temp1 = New Byte(31) {}
Dim temp2 = New Byte(63) {}
Dim temp3 = New Byte(63) {}
Cpy32(temp1, ORDER)
Cpy32(s, Egcd32(temp2, temp3, s, temp1))
If (s(31) And &H80) <> 0 Then Mula_Small(s, s, 0, ORDER, 32, 1)
End If
End Sub
' smallest multiple of the order that's >= 2^255
Private Shared ReadOnly ORDER_TIMES_8 As Byte() = {104, 159, 174, 231, 210, 24, 147, 192, 178, 230, 188, 23, 245, 206, 247, 166, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 128}
' constants 2Gy and 1/(2Gy)
Private Shared ReadOnly BASE_2Y As Long10 = New Long10(39999547, 18689728, 59995525, 1648697, 57546132, 24010086, 19059592, 5425144, 63499247, 16420658)
Private Shared ReadOnly BASE_R2Y As Long10 = New Long10(5744, 8160848, 4790893, 13779497, 35730846, 12541209, 49101323, 30047407, 40071253, 6226132)
End Class

evolver · 2. April 2021, 10:09

Ich brech ins Essen! Da kommt er mit einem voll funktionsfähigem Komplettcode um die Ecke und vernichtet mal eben so meine monatelange Arbeit daran mit einem Fingerschnippen und dem Vermerk: "hi, da war jemand schneller als du, lass es lieber ganz bleiben mit dem programmieren und werde Jurist und befasse dich mit Lizenzen..." NEIN, einfach NEIN

! Zum Einen finde ich das Saustark :thumbsup:

! Zum anderen jedoch echt uncool :thumbdown:

. Aber gut gegoogelt ist halb gecodet und deswegen geht der Punkt an dich!

Dankeschön exc-jdbi

exc-jdbi · 2. April 2021, 11:51

@evolver

Sorry, wollte ganz bestimmt nicht deinen Unmut steigern. Vielleicht wäre es auch sinnvoller gewesen, dir den Hinweis per PM zu kommen zu lassen. (Bin auch zufällig darüber gestolpert)

Abgesehen von der Lizenz, darf man sicher mal den Code testen (darüber steht nicht einmal was) und schauen, was es mit der ECKCDSA auf sich hat und das mit den Infos von Wikipedia vergleichen. en.wikipedia.org/wiki/KCDSA

Ausserdem ist der Code zum Teil "hundslausig" übersetzt, und jedem Vb.Net Profi würden gleich die Tränen in die Augen schiessen.

Das Ganze (der GrundCode) lässt sich mMn um einiges verschönern, indem mehr mit den Bordmittel von .Net gearbeitet wird. (Async/Await, ActionOfT, FuncOfT, Anonyme Methoden, Klassen, Extentions, etc.)

Was nun genau der Fehler (Test_Equal ungleiche Arrays) auf sich hat in der Signierung, bin ich noch nicht dahinter gekommen wo das Problem liegt, da ich mich mit dem Code und der Mathematik noch nicht beschäftigt habe. Es ist aber anscheinend nur die Signierung die diesen Fehler hervorruft.

Daher meine Intension: Bitte nicht aufgeben und dran bleiben, und deine Arbeit fortsetzen, denn schlussendlich lernt man ja auch viel über die Umsetzung, das mathematisches Vorgehen, Konzeption, und überhaupt alles, was nicht sofort ersichtlich und offensichtlich etc. ist.

Freundliche Grüsse

exc-jdbi

evolver · 2. April 2021, 13:01

hallo,
ich schrieb ja bereits, dass das Signieren schon läuft. Tausche einfach mal die "Sign"-Methode durch folgende aus und es funzt (zumind. bei mir), wenn du noch dran interessiert bist:

Spoiler anzeigen

Quellcode

Public Shared Function Sign(ByVal h As Byte(), ByVal x As Byte(), ByVal s As Byte()) As Byte()
' v = (x - h) s Mod q
Dim h1(31) As Byte
Dim x1(31) As Byte
Dim Dummy1(31) As Byte
Dim Dummy2(31) As Byte
Dim Temp_v(63) As Byte
Dim Dummy3(63) As Byte
' Don't clobber the arguments, be nice!
h1 = h.ToArray 'h1 = h
x1 = x.ToArray 'x1 = x
' Reduce modulo group order
DivMod(Dummy1, h1, 32, ORDER, 32)
DivMod(Dummy2, x1, 32, ORDER, 32)
' v = x1 - h1
' If v Is negative, add the group order to it to become positive.
' If v was already positive we don't have to worry about overflow
' when adding the order because v < ORDER And 2*ORDER < 2^256
Dim v(31) As Byte
Mula_Small(v, x1, 0, h1, 32, -1)
Mula_Small(v, v, 0, ORDER, 32, 1)
' Temp_v = (x-h)*s Mod q
Mula32(Temp_v, v, s, 32, 1)
DivMod(Dummy3, Temp_v, 64, ORDER, 32)
Dim w As Boolean = False
For i As Integer = 0 To 31
v(i) = Temp_v(i)
w = w Or CBool(v(i))
Next
If w <> False Then
Return v
Else
Return Nothing
End If
End Function

Beste Grüße

exc-jdbi · 2. April 2021, 13:42

Sieht so auf den ersten Blick gut aus :thumbsup:

Habs jetzt einfach schnell umgeschrieben, hoffe das es kein Fehler hat.

VB.NET-Quellcode

Public Shared Function Sign(v As Byte(), h As Byte(), x As Byte(), s As Byte()) As Boolean
' v = (x - h) s mod q
Dim w, i As Int32
Array.Clear(v, 0, v.Length)
Dim hh = h.ToArray 'h1 = h
Dim xx = x.ToArray 'x1 = x
' Reduce modulo group order
Dim Dummy1 = New Byte(31) {}
Dim Dummy2 = New Byte(31) {}
DivMod(Dummy1, hh, 32, ORDER, 32)
DivMod(Dummy2, xx, 32, ORDER, 32)
' v = x1 - h1
' If v Is negative, add the group order to it to become positive.
' If v was already positive we don't have to worry about overflow
' when adding the order because v < ORDER And 2*ORDER < 2^256
Dim tmp1 = New Byte(63) {}
Dim tmp2 = New Byte(63) {}
i = Mula_Small(v, xx, 0, hh, 32, -1)
'Mula_Small(v, v, 0, ORDER, 32, (15 - v(31)) \ 16)
Mula_Small(v, v, 0, ORDER, 32, 1)
Mula32(tmp1, v, s, 32, 1)
DivMod(tmp2, tmp1, 64, ORDER, 32)
w = 0
i = 0
While i < 32
v(i) = tmp1(i)
w = w Or v(i)
i += 1
End While
Return w <> 0
End Function

evolver · 2. April 2021, 14:55

Der Code funzt nun. Aber er sieht noch echt aus wie unterm Sofa hervorgeholt. Zumal das EC-KCDSA nun einfach mit in der Curve25519 mit hinzugekritzelt ist (börgs). Das muss jetzt noch schön gemacht werden. Und wenn das fertig ist, dann können wir uns noch mal genauer mit der Lizenz auseinander setzen.

Stay Tuned...

exc-jdbi · 2. April 2021, 15:41

Ich finde man darf ruhig zeigen, dass es unterschiedliche Programmiersprachen gibt, die Codes auch unterschiedlich interpretieren.

Mein Java-Programm ist schon länger nicht mehr auf meinem System, auch wenn es eine sehr gute Sprache ist. Dafür habe ich angefangen mit C#, und bis jetzt bin ich sehr zufrieden mit dieser Sprache.
Ob der Code auf dem oben erwähnten Link funktioniert in Java, kann ich leider nicht beurteilen. Fakt ist aber, dass es in C# nicht funktioniert, und zum Glück gibt es viele andere User wie dich, die sich gerne mit der Materie beschäftigen.

Klar muss man Lizenzen beachten. Aber solange man sich nur mit der Technik und der Mathematik beschäftigt (sofern erlaubt), und keinem mutwillig einen Schaden unterjubelt gibts auch hier genug Freiraum der genutzt werden darf, um die Interessen zu dieser Materie im gegenseitigen Interesse aller zu wahren.

Freundliche Grüsse

exc-jdbi

ECKCDSA von JavaScript zu VB.NET

ECKCDSA von JavaScript zu VB.NET

Quellcode

Quellcode

Quellcode

Quellcode

VB.NET-Quellcode

Ähnliche Themen

2 Benutzer haben hier geschrieben