Curve25519 von C# nach VB.NET

  • VB.NET

Es gibt 18 Antworten in diesem Thema. Der letzte Beitrag () ist von evolver.

    Curve25519 von C# nach VB.NET

    Hallo wertes Forum,
    ich bin neu hier und lese hier schon seit mehreren Jahren anonym in verschiedenen Themen mit, die mir teilweise immer wieder gut geholfen haben. Nun jedoch stehe ich vor einer Aufgabe, die mir etwas schwer fällt.

    ich versuche eine Übersetzung einer Klasse in C# nach VB.NET. Dabei handelt es sich um eine Cryptografische Elliptische Kurve, wie sie auf GitHub zu finden ist:
    github.com/hanswolff/curve2551…/Curve25519/Curve25519.cs

    Mir ist beim umschreiben und tracen/debuggen aufgefallen, das es dort doch einige größere Unterscheide gibt.
    Zum Beispiel in der Methode "Pack" :

    Quellcode

    1. long t = ld + x.N0 + (x.N1 << 26);
    2. m[0] = (byte)t;
    3. m[1] = (byte)(t >> 8);
    4. m[2] = (byte)(t >> 16);
    5. m[3] = (byte)(t >> 24);


    das Würde bei einer 1:1 Schreibweise folgendes ergeben:

    Quellcode

    1. Dimt As long = ld + x.N0 + (x.N1 << 26)
    2. m(0) = CByte(t)
    3. m(1) = CByte(t >> 8)
    4. m(2) = CByte(t >> 16)
    5. m(3) = CByte(t >> 24)


    was wiederum zu einem Überlauf-Crash führt. so habe ich folgende Lösung dafür gefunden:

    Quellcode

    1. Dim t As Long = ld + x.N0 + (x.N1 << 26)
    2. Dim test = BitConverter.GetBytes(t)
    3. m(0) = test(0)
    4. m(1) = test(1)
    5. m(2) = test(2)
    6. m(3) = test(3)


    Das liefert auch das richtige Ergebnis (in dem Fall einen Public Key)

    Schwer wird es, wenn man den SignKey erstellen will. U.a. kommen hier Methoden zur Anwendung wie z.b. "MulSmall", "Multiply" und "Square".
    Ich bekomme es nicht hin, den richtigen Key damit zu erstellen. Ich habe das Gefühl, dass irgendwas mit der Bitwise-Verschiebung nicht hinhaut.

    Da meine Mathekenntnisse dort doch etwas eingeschränkt sind, dachte ich vllt gibt es hier jmd, der ein wenig mehr Ahnung von der Matherie hat als ich.

    Zum Hintergrund:
    Ich möchte damit bei der Entwicklung einer Kryptowährung mithelfen und bin dabei ein Projekt zu entwickeln.

    Beste Grüße ins Forum :)
    Willkommen im Forum. :thumbup:

    evolver schrieb:

    Ich habe das Gefühl, dass irgendwas mit der Bitwise-Verschiebung nicht hinhaut.
    Ich würde mal behaupten, dass genau das sicher funktioniert.
    Probleme gibt es eher beim impliziten Casten auf einen anderen Datentyp.
    Wenn Du Probleme in der Entwicklungsumgebung hast, wäre es praktisch, Du hast eine C#-Vorlage, die Du gegen Deinen VB.NET-Code testen kannst.
    Also 2 Entwicklungsumgebungen starten, eine mit der C#-Vorlage und eine mit Deinem VB-Code und dann beide Programme simultan zeilenweise abarbeiten.
    Ansonsten poste beide Codes und gib dazu einen Datensatz an, bei dem es knallt.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    ok ich habe nun die Bitwise verschiebungen wieder eingebaut und die klammern nochmal alle überprüft und nun läufts in den 3 besagten Methoden durch. Es kracht nun in einer anderen Methode "DivMod" wegen eines OutOfRange-zugriffs in Zeile 342. Nach kurzem hochscrollen erkennt man auch warum das so ist:

    /* 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 */

    ich habe mal versucht mit ReDim Preserve und Exit Sub durch zu kommen... der SignKey ist dann jedoch falsch :\
    wie bekommt man denn -1 als gültigen arrayzugriff in VB hin?
    @evolver Das ganze ist ein Kommentar.
    Gibt es da auch Code?
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    hallo,
    ich hatte eig. die zahl mit einem Link zum C#-code versehen (github.com/hanswolff/curve2551…e25519/Curve25519.cs#L243)

    mein code sieht ähnlich aus, aber ich kann ihn hier noch einmal reinsetzen:

    VB.NET-Quellcode

    1. ' divide r (size n) by d (size t), returning quotient q and remainder r
    2. ' quotient is size n-t+1, remainder is size t
    3. ' requires t > 0 && d[t-1] != 0
    4. ' requires that r[-1] and d[-1] are valid memory locations
    5. ' q may overlap with r+t
    6. Public Shared Sub DivMod(ByRef q As Byte(), ByRef r As Byte(), ByRef n As Integer, ByRef d As Byte(), ByRef t As Integer)
    7. Dim rn As Integer = 0
    8. Dim dt As Integer = (d(t - 1) And &HFF) << 8
    9. If t > 1 Then
    10. dt = dt Or d(t - 2) And &HFF
    11. End If
    12. While n >= t
    13. n -= 1
    14. If n = -1 Then
    15. 'Exit Sub '<<<<<< hinzugefügt zum debug/test
    16. End If
    17. Dim z As Integer = (rn << 16) Or ((r(n) And &HFF) << 8)
    18. If n > 0 Then
    19. z = z Or r(n) And &HFF
    20. End If
    21. z /= dt
    22. rn += MultiplyArraySmall(r, r, n - t + 1, d, t, -z)
    23. Dim temp = CByte(z + rn And &HFF)
    24. Dim temp1 = n - t + 1
    25. If q.Length - 1 < temp1 Then
    26. 'ReDim Preserve q(temp1) ' <<<<<<<< hinzugefügt zum debug/test
    27. End If
    28. q(temp1) = temp ' rn is 0 or -1 (underflow)
    29. MultiplyArraySmall(r, r, n - t + 1, d, t, -rn)
    30. rn = r(n) And &HFF
    31. r(n) = 0
    32. End While
    33. r(t - 1) = CByte(rn)
    34. End Sub

    in Zeile 38 krachts dann...

    evolver schrieb:

    in Zeile 38 krachts dann...
    Schön.
    Mit welchen Werten / Parametern muss ich Deinen Code aufrufen, damit es bei mir ebenfalls knallt?
    Dies hier scheint mir ein natives Stück Code C / C++ zu sein, das kannst Du nicht einfach so nach .NET überführen:

    evolver schrieb:

    VB.NET-Quellcode

    1. ' requires that r[-1] and d[-1] are valid memory locations



    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!
    hallo,
    ich habe noch einmal die Parameter und dessen Übergabe überprüft und dabei festgestellt, dass ich das alles noch als Referenzparameter übergeben habe (ByRef). aus der C# Quelle fällt es mir schwer diese von "ByVal" zu unterscheiden. Was ich aber sagen kann, ist das alles von der Methode "Egcd32" aus zu gehen scheint (github.com/hanswolff/curve2551…e25519/Curve25519.cs#L268). Nach dem ich die Parameter überprüft und versucht habe Referenzparameter von Übergabeparametern zu trennen, krachts nun in der doch recht übersichtlichen Methode "GetNumSize" ebenfalls wegen eines OutOfRange-zugriffs eines Arrays:

    VB.NET-Quellcode

    1. Private Shared Function GetNumSize(ByVal num As Byte(), ByVal maxSize As Integer) As Integer
    2. Dim i As Integer = maxSize
    3. While i >= 0
    4. If num(i) = 0 Then '<<<<<<< krachbumm
    5. Return i + 1
    6. End If
    7. i += 1
    8. End While
    9. Return 0
    10. End Function


    Als Parameter "num" kommt dort ein ByteArray an mit einer länge von 32 und folgendem Inhalt:
    {237, 211, 245, 92, 26, 99, 18, 88, 214, 156, 247, 162, 222, 149, 222, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 16}
    und als "maxSize" kommt dort der integer mit dem Wert 32 an. Mir scheint es logisch zu sein, warum es dort kracht, jedoch nicht, warum das in der C# quelle so laufen kann (github.com/hanswolff/curve2551…e25519/Curve25519.cs#L251)
    du hast iwie schwierigkeiten, fehlermeldungen genau zu zitieren, was?
    Also die zeile ist nun gut erkenntlich gemacht, aber dass die Fehlermeldung krachbum lautet kauf ich dir nicht ab.

    nagut, es wird eine indexOutOfRangeException sein, das sieht man auch so.
    darf man nun auch den entsprechenden c#-code sehen?
    hallo,
    es kommt die Fehlermeldung:
    System.IndexOutOfRangeException: "Der Index war außerhalb des Arraybereichs."

    etwas ausführlicher:

    Quellcode

    1. - $exception {"Der Index war außerhalb des Arraybereichs."} System.IndexOutOfRangeException
    2. + Data {System.Collections.ListDictionaryInternal} System.Collections.IDictionary {System.Collections.ListDictionaryInternal}
    3. HResult -2146233080 Integer
    4. HelpLink Nothing String
    5. + IPForWatsonBuckets &H00000000 System.UIntPtr
    6. + InnerException Nothing System.Exception
    7. IsTransient False Boolean
    8. Message "Der Index war außerhalb des Arraybereichs." String
    9. RemoteStackTrace Nothing String
    10. Source "curvesecure" String
    11. StackTrace " bei curvesecure.Elliptic.RefCurve25519.GetNumSize(Byte[] num, Int32 maxSize) in C:\curvesecure\curvesecure\Tools\Curve25519.vb:Zeile 1169." & vbCrLf & " bei curvesecure.Elliptic.RefCurve25519.Egcd32(Byte[]& x, Byte[]& y, Byte[]& a, Byte[]& b) in C:\curvesecure\curvesecure\Tools\Curve25519.vb:Zeile 1242." & vbCrLf & " bei curvesecure.Elliptic.RefCurve25519.Core(Byte[]& publicKey, Byte[]& signingKey, Byte[]& privateKey, Byte[]& peerPublicKey) in C:\curvesecure\curvesecure\Tools\Curve25519.vb:Zeile 1804." & vbCrLf & " bei curvesecure.ECKCDSA.keygen(Object& k) in C:\curvesecure\curvesecure\Tools\ECKCDSA.vb:Zeile 192." & vbCrLf & " bei curvesecure.Form1.generateMasterKeys(String passPhrase) in C:\curvesecure\curvesecure\Form1.vb:Zeile 104." & vbCrLf & " bei curvesecure.Form1.Button1_Click(Object sender, EventArgs e) in C:\curvesecure\curvesecure\Form1.vb:Zeile 15." & vbCrLf & " bei System.Windows.Forms.Control.OnClick(EventArgs e)" & vbCrLf & " bei System.Windows.Forms.Button.OnClick(EventArgs e)" & vbCrLf & " bei System.Windows.Forms.Button.OnMouseUp(MouseEventArgs mevent)" & vbCrLf & " bei System.Windows.Forms.Control.WmMouseUp(Message& m, MouseButtons button, Int32 clicks)" & vbCrLf & " bei System.Windows.Forms.Control.WndProc(Message& m)" & vbCrLf & " bei System.Windows.Forms.ButtonBase.WndProc(Message& m)" & vbCrLf & " bei System.Windows.Forms.Button.WndProc(Message& m)" & vbCrLf & " bei System.Windows.Forms.Control.ControlNativeWindow.OnMessage(Message& m)" & vbCrLf & " bei System.Windows.Forms.Control.ControlNativeWindow.WndProc(Message& m)" & vbCrLf & " bei System.Windows.Forms.NativeWindow.DebuggableCallback(IntPtr hWnd, Int32 msg, IntPtr wparam, IntPtr lparam)" & vbCrLf & " bei System.Windows.Forms.UnsafeNativeMethods.DispatchMessageW(MSG& msg)" & vbCrLf & " bei System.Windows.Forms.Application.ComponentManager.System.Windows.Forms.UnsafeNativeMethods.IMsoComponentManager.FPushMessageLoop(IntPtr dwComponentID, Int32 reason, Int32 pvLoopData)" & vbCrLf & " bei System.Windows.Forms.Application.ThreadContext.RunMessageLoopInner(Int32 reason, ApplicationContext context)" & vbCrLf & " bei System.Windows.Forms.Application.ThreadContext.RunMessageLoop(Int32 reason, ApplicationContext context)" & vbCrLf & " bei Microsoft.VisualBasic.ApplicationServices.WindowsFormsApplicationBase.OnRun()" & vbCrLf & " bei Microsoft.VisualBasic.ApplicationServices.WindowsFormsApplicationBase.DoApplicationModel()" & vbCrLf & " bei Microsoft.VisualBasic.ApplicationServices.WindowsFormsApplicationBase.Run(String[] commandLine)" & vbCrLf & " bei curvesecure.My.MyApplication.Main(String[] Args) in :Zeile 81." String
    12. + TargetSite {Int32 GetNumSize(Byte[], Int32)} System.Reflection.MethodBase {System.Reflection.RuntimeMethodInfo}
    13. + WatsonBuckets {Length=5616} Object {Byte()}
    14. _HResult -2146233080 Integer
    15. _className Nothing String
    16. + _data {System.Collections.ListDictionaryInternal} System.Collections.IDictionary {System.Collections.ListDictionaryInternal}
    17. _dynamicMethods Nothing Object
    18. + _exceptionMethod {Int32 GetNumSize(Byte[], Int32)} System.Reflection.MethodBase {System.Reflection.RuntimeMethodInfo}
    19. _exceptionMethodString Nothing String
    20. _helpURL Nothing String
    21. + _innerException Nothing System.Exception
    22. + _ipForWatsonBuckets &H00000000 System.UIntPtr
    23. _message "Der Index war außerhalb des Arraybereichs." String
    24. _remoteStackIndex 0 Integer
    25. _remoteStackTraceString Nothing String
    26. + _safeSerializationManager {System.Runtime.Serialization.SafeSerializationManager} System.Runtime.Serialization.SafeSerializationManager
    27. _source "curvesecure" String
    28. + _stackTrace {Length=768} Object {SByte()}
    29. _stackTraceString Nothing String
    30. + _watsonBuckets {Length=5616} Object {Byte()}
    31. _xcode -532462766 Integer
    32. + _xptrs &H00000000 System.IntPtr
    33. + Freigegebene Member
    hallo ErfinderDesRades,
    es ist schon recht komisch, scheinbar funzen die externen Links bei dir nicht?

    Aber ich helfe da gern aus (sofern das Forum das zulässt):

    Spoiler anzeigen

    Quellcode

    1. /* Ported parts from Java to C# and refactored by Hans Wolff, 17/09/2013 */
    2. /* Ported from C to Java by Dmitry Skiba [sahn0], 23/02/08.
    3. * Original: http://code.google.com/p/curve25519-java/
    4. */
    5. /* Generic 64-bit integer implementation of Curve25519 ECDH
    6. * Written by Matthijs van Duin, 200608242056
    7. * Public domain.
    8. *
    9. * Based on work by Daniel J Bernstein, http://cr.yp.to/ecdh.html
    10. */
    11. using System;
    12. using System.Security.Cryptography;
    13. namespace Elliptic
    14. {
    15. public class Curve25519
    16. {
    17. /* key size */
    18. public const int KeySize = 32;
    19. /* group order (a prime near 2^252+2^124) */
    20. static readonly byte[] Order =
    21. {
    22. 237, 211, 245, 92,
    23. 26, 99, 18, 88,
    24. 214, 156, 247, 162,
    25. 222, 249, 222, 20,
    26. 0, 0, 0, 0,
    27. 0, 0, 0, 0,
    28. 0, 0, 0, 0,
    29. 0, 0, 0, 16
    30. };
    31. /********* KEY AGREEMENT *********/
    32. /// <summary>
    33. /// Private key clamping (inline, for performance)
    34. /// </summary>
    35. /// <param name="key">[out] 32 random bytes</param>
    36. public static void ClampPrivateKeyInline(byte[] key)
    37. {
    38. if (key == null) throw new ArgumentNullException("key");
    39. if (key.Length != 32) throw new ArgumentException(String.Format("key must be 32 bytes long (but was {0} bytes long)", key.Length));
    40. key[31] &= 0x7F;
    41. key[31] |= 0x40;
    42. key[0] &= 0xF8;
    43. }
    44. /// <summary>
    45. /// Private key clamping
    46. /// </summary>
    47. /// <param name="rawKey">[out] 32 random bytes</param>
    48. public static byte[] ClampPrivateKey(byte[] rawKey)
    49. {
    50. if (rawKey == null) throw new ArgumentNullException("rawKey");
    51. if (rawKey.Length != 32) throw new ArgumentException(String.Format("rawKey must be 32 bytes long (but was {0} bytes long)", rawKey.Length), "rawKey");
    52. var res = new byte[32];
    53. Array.Copy(rawKey, res, 32);
    54. res[31] &= 0x7F;
    55. res[31] |= 0x40;
    56. res[0] &= 0xF8;
    57. return res;
    58. }
    59. /// <summary>
    60. /// Creates a random private key
    61. /// </summary>
    62. /// <returns>32 random bytes that are clamped to a suitable private key</returns>
    63. public static byte[] CreateRandomPrivateKey()
    64. {
    65. var privateKey = new byte[32];
    66. RNGCryptoServiceProvider.Create().GetBytes(privateKey);
    67. ClampPrivateKeyInline(privateKey);
    68. return privateKey;
    69. }
    70. /// <summary>
    71. /// Key-pair generation (inline, for performance)
    72. /// </summary>
    73. /// <param name="publicKey">[out] public key</param>
    74. /// <param name="signingKey">[out] signing key (ignored if NULL)</param>
    75. /// <param name="privateKey">[out] private key</param>
    76. /// <remarks>WARNING: if signingKey is not NULL, this function has data-dependent timing</remarks>
    77. public static void KeyGenInline(byte[] publicKey, byte[] signingKey, byte[] privateKey)
    78. {
    79. if (publicKey == null) throw new ArgumentNullException("publicKey");
    80. if (publicKey.Length != 32) throw new ArgumentException(String.Format("publicKey must be 32 bytes long (but was {0} bytes long)", publicKey.Length), "publicKey");
    81. if (signingKey == null) throw new ArgumentNullException("signingKey");
    82. if (signingKey.Length != 32) throw new ArgumentException(String.Format("signingKey must be 32 bytes long (but was {0} bytes long)", signingKey.Length), "signingKey");
    83. if (privateKey == null) throw new ArgumentNullException("privateKey");
    84. if (privateKey.Length != 32) throw new ArgumentException(String.Format("privateKey must be 32 bytes long (but was {0} bytes long)", privateKey.Length), "privateKey");
    85. RNGCryptoServiceProvider.Create().GetBytes(privateKey);
    86. ClampPrivateKeyInline(privateKey);
    87. Core(publicKey, signingKey, privateKey, null);
    88. }
    89. /// <summary>
    90. /// Generates the public key out of the clamped private key
    91. /// </summary>
    92. /// <param name="privateKey">private key (must use ClampPrivateKey first!)</param>
    93. public static byte[] GetPublicKey(byte[] privateKey)
    94. {
    95. var publicKey = new byte[32];
    96. Core(publicKey, null, privateKey, null);
    97. return publicKey;
    98. }
    99. /// <summary>
    100. /// Generates signing key out of the clamped private key
    101. /// </summary>
    102. /// <param name="privateKey">private key (must use ClampPrivateKey first!)</param>
    103. public static byte[] GetSigningKey(byte[] privateKey)
    104. {
    105. var signingKey = new byte[32];
    106. var publicKey = new byte[32];
    107. Core(publicKey, signingKey, privateKey, null);
    108. return signingKey;
    109. }
    110. /// <summary>
    111. /// Key agreement
    112. /// </summary>
    113. /// <param name="privateKey">[in] your private key for key agreement</param>
    114. /// <param name="peerPublicKey">[in] peer's public key</param>
    115. /// <returns>shared secret (needs hashing before use)</returns>
    116. public static byte[] GetSharedSecret(byte[] privateKey, byte[] peerPublicKey)
    117. {
    118. var sharedSecret = new byte[32];
    119. Core(sharedSecret, null, privateKey, peerPublicKey);
    120. return sharedSecret;
    121. }
    122. ///////////////////////////////////////////////////////////////////////////
    123. /* sahn0:
    124. * Using this class instead of long[10] to avoid bounds checks. */
    125. private sealed class Long10
    126. {
    127. public Long10()
    128. {
    129. }
    130. public Long10(
    131. long n0, long n1, long n2, long n3, long n4,
    132. long n5, long n6, long n7, long n8, long n9)
    133. {
    134. N0 = n0;
    135. N1 = n1;
    136. N2 = n2;
    137. N3 = n3;
    138. N4 = n4;
    139. N5 = n5;
    140. N6 = n6;
    141. N7 = n7;
    142. N8 = n8;
    143. N9 = n9;
    144. }
    145. public long N0, N1, N2, N3, N4, N5, N6, N7, N8, N9;
    146. }
    147. /********************* radix 2^8 math *********************/
    148. static void Copy32(byte[] source, byte[] destination)
    149. {
    150. Array.Copy(source, 0, destination, 0, 32);
    151. }
    152. /* p[m..n+m-1] = q[m..n+m-1] + z * x */
    153. /* n is the size of x */
    154. /* n+m is the size of p and q */
    155. static int MultiplyArraySmall(byte[] p, byte[] q, int m, byte[] x, int n, int z)
    156. {
    157. int v = 0;
    158. for (int i = 0; i < n; ++i)
    159. {
    160. v += (q[i + m] & 0xFF) + z * (x[i] & 0xFF);
    161. p[i + m] = (byte)v;
    162. v >>= 8;
    163. }
    164. return v;
    165. }
    166. /* p += x * y * z where z is a small integer
    167. * x is size 32, y is size t, p is size 32+t
    168. * y is allowed to overlap with p+32 if you don't care about the upper half */
    169. static void MultiplyArray32(byte[] p, byte[] x, byte[] y, int t, int z)
    170. {
    171. const int n = 31;
    172. int w = 0;
    173. int i = 0;
    174. for (; i < t; i++)
    175. {
    176. int zy = z * (y[i] & 0xFF);
    177. w += MultiplyArraySmall(p, p, i, x, n, zy) +
    178. (p[i + n] & 0xFF) + zy * (x[n] & 0xFF);
    179. p[i + n] = (byte)w;
    180. w >>= 8;
    181. }
    182. p[i + n] = (byte)(w + (p[i + n] & 0xFF));
    183. }
    184. /* divide r (size n) by d (size t), returning quotient q and remainder r
    185. * quotient is size n-t+1, remainder is size t
    186. * requires t > 0 && d[t-1] != 0
    187. * requires that r[-1] and d[-1] are valid memory locations
    188. * q may overlap with r+t */
    189. static void DivMod(byte[] q, byte[] r, int n, byte[] d, int t)
    190. {
    191. int rn = 0;
    192. int dt = ((d[t - 1] & 0xFF) << 8);
    193. if (t > 1)
    194. {
    195. dt |= (d[t - 2] & 0xFF);
    196. }
    197. while (n-- >= t)
    198. {
    199. int z = (rn << 16) | ((r[n] & 0xFF) << 8);
    200. if (n > 0)
    201. {
    202. z |= (r[n - 1] & 0xFF);
    203. }
    204. z /= dt;
    205. rn += MultiplyArraySmall(r, r, n - t + 1, d, t, -z);
    206. q[n - t + 1] = (byte)((z + rn) & 0xFF); /* rn is 0 or -1 (underflow) */
    207. MultiplyArraySmall(r, r, n - t + 1, d, t, -rn);
    208. rn = (r[n] & 0xFF);
    209. r[n] = 0;
    210. }
    211. r[t - 1] = (byte)rn;
    212. }
    213. static int GetNumSize(byte[] num, int maxSize)
    214. {
    215. for (int i = maxSize; i >= 0; i++)
    216. {
    217. if (num[i] == 0) return i + 1;
    218. }
    219. return 0;
    220. }
    221. /// <summary>
    222. /// Returns x if a contains the gcd, y if b.
    223. /// </summary>
    224. /// <param name="x">x and y must have 64 bytes space for temporary use.</param>
    225. /// <param name="y">x and y must have 64 bytes space for temporary use.</param>
    226. /// <param name="a">requires that a[-1] and b[-1] are valid memory locations</param>
    227. /// <param name="b">requires that a[-1] and b[-1] are valid memory locations</param>
    228. /// <returns>Also, the returned buffer contains the inverse of a mod b as 32-byte signed.</returns>
    229. static byte[] Egcd32(byte[] x, byte[] y, byte[] a, byte[] b)
    230. {
    231. int bn = 32;
    232. int i;
    233. for (i = 0; i < 32; i++)
    234. x[i] = y[i] = 0;
    235. x[0] = 1;
    236. int an = GetNumSize(a, 32);
    237. if (an == 0)
    238. return y; /* division by zero */
    239. var temp = new byte[32];
    240. while (true)
    241. {
    242. int qn = bn - an + 1;
    243. DivMod(temp, b, bn, a, an);
    244. bn = GetNumSize(b, bn);
    245. if (bn == 0)
    246. return x;
    247. MultiplyArray32(y, x, temp, qn, -1);
    248. qn = an - bn + 1;
    249. DivMod(temp, a, an, b, bn);
    250. an = GetNumSize(a, an);
    251. if (an == 0)
    252. return y;
    253. MultiplyArray32(x, y, temp, qn, -1);
    254. }
    255. }
    256. /********************* radix 2^25.5 GF(2^255-19) math *********************/
    257. private const int P25 = 33554431; /* (1 << 25) - 1 */
    258. private const int P26 = 67108863; /* (1 << 26) - 1 */
    259. /* Convert to internal format from little-endian byte format */
    260. static void Unpack(Long10 x, byte[] m)
    261. {
    262. x.N0 = ((m[0] & 0xFF)) | ((m[1] & 0xFF)) << 8 |
    263. (m[2] & 0xFF) << 16 | ((m[3] & 0xFF) & 3) << 24;
    264. x.N1 = ((m[3] & 0xFF) & ~3) >> 2 | (m[4] & 0xFF) << 6 |
    265. (m[5] & 0xFF) << 14 | ((m[6] & 0xFF) & 7) << 22;
    266. x.N2 = ((m[6] & 0xFF) & ~7) >> 3 | (m[7] & 0xFF) << 5 |
    267. (m[8] & 0xFF) << 13 | ((m[9] & 0xFF) & 31) << 21;
    268. x.N3 = ((m[9] & 0xFF) & ~31) >> 5 | (m[10] & 0xFF) << 3 |
    269. (m[11] & 0xFF) << 11 | ((m[12] & 0xFF) & 63) << 19;
    270. x.N4 = ((m[12] & 0xFF) & ~63) >> 6 | (m[13] & 0xFF) << 2 |
    271. (m[14] & 0xFF) << 10 | (m[15] & 0xFF) << 18;
    272. x.N5 = (m[16] & 0xFF) | (m[17] & 0xFF) << 8 |
    273. (m[18] & 0xFF) << 16 | ((m[19] & 0xFF) & 1) << 24;
    274. x.N6 = ((m[19] & 0xFF) & ~1) >> 1 | (m[20] & 0xFF) << 7 |
    275. (m[21] & 0xFF) << 15 | ((m[22] & 0xFF) & 7) << 23;
    276. x.N7 = ((m[22] & 0xFF) & ~7) >> 3 | (m[23] & 0xFF) << 5 |
    277. (m[24] & 0xFF) << 13 | ((m[25] & 0xFF) & 15) << 21;
    278. x.N8 = ((m[25] & 0xFF) & ~15) >> 4 | (m[26] & 0xFF) << 4 |
    279. (m[27] & 0xFF) << 12 | ((m[28] & 0xFF) & 63) << 20;
    280. x.N9 = ((m[28] & 0xFF) & ~63) >> 6 | (m[29] & 0xFF) << 2 |
    281. (m[30] & 0xFF) << 10 | (m[31] & 0xFF) << 18;
    282. }
    283. /// <summary>
    284. /// Check if reduced-form input >= 2^255-19
    285. /// </summary>
    286. static bool IsOverflow(Long10 x)
    287. {
    288. return (
    289. ((x.N0 > P26 - 19)) &
    290. ((x.N1 & x.N3 & x.N5 & x.N7 & x.N9) == P25) &
    291. ((x.N2 & x.N4 & x.N6 & x.N8) == P26)
    292. ) || (x.N9 > P25);
    293. }
    294. /* Convert from internal format to little-endian byte format. The
    295. * number must be in a reduced form which is output by the following ops:
    296. * unpack, mul, sqr
    297. * set -- if input in range 0 .. P25
    298. * If you're unsure if the number is reduced, first multiply it by 1. */
    299. static void Pack(Long10 x, byte[] m)
    300. {
    301. int ld = (IsOverflow(x) ? 1 : 0) - ((x.N9 < 0) ? 1 : 0);
    302. int ud = ld * -(P25 + 1);
    303. ld *= 19;
    304. long t = ld + x.N0 + (x.N1 << 26);
    305. m[0] = (byte)t;
    306. m[1] = (byte)(t >> 8);
    307. m[2] = (byte)(t >> 16);
    308. m[3] = (byte)(t >> 24);
    309. t = (t >> 32) + (x.N2 << 19);
    310. m[4] = (byte)t;
    311. m[5] = (byte)(t >> 8);
    312. m[6] = (byte)(t >> 16);
    313. m[7] = (byte)(t >> 24);
    314. t = (t >> 32) + (x.N3 << 13);
    315. m[8] = (byte)t;
    316. m[9] = (byte)(t >> 8);
    317. m[10] = (byte)(t >> 16);
    318. m[11] = (byte)(t >> 24);
    319. t = (t >> 32) + (x.N4 << 6);
    320. m[12] = (byte)t;
    321. m[13] = (byte)(t >> 8);
    322. m[14] = (byte)(t >> 16);
    323. m[15] = (byte)(t >> 24);
    324. t = (t >> 32) + x.N5 + (x.N6 << 25);
    325. m[16] = (byte)t;
    326. m[17] = (byte)(t >> 8);
    327. m[18] = (byte)(t >> 16);
    328. m[19] = (byte)(t >> 24);
    329. t = (t >> 32) + (x.N7 << 19);
    330. m[20] = (byte)t;
    331. m[21] = (byte)(t >> 8);
    332. m[22] = (byte)(t >> 16);
    333. m[23] = (byte)(t >> 24);
    334. t = (t >> 32) + (x.N8 << 12);
    335. m[24] = (byte)t;
    336. m[25] = (byte)(t >> 8);
    337. m[26] = (byte)(t >> 16);
    338. m[27] = (byte)(t >> 24);
    339. t = (t >> 32) + ((x.N9 + ud) << 6);
    340. m[28] = (byte)t;
    341. m[29] = (byte)(t >> 8);
    342. m[30] = (byte)(t >> 16);
    343. m[31] = (byte)(t >> 24);
    344. }
    345. /// <summary>
    346. /// Copy a number
    347. /// </summary>
    348. static void Copy(Long10 numOut, Long10 numIn)
    349. {
    350. numOut.N0 = numIn.N0;
    351. numOut.N1 = numIn.N1;
    352. numOut.N2 = numIn.N2;
    353. numOut.N3 = numIn.N3;
    354. numOut.N4 = numIn.N4;
    355. numOut.N5 = numIn.N5;
    356. numOut.N6 = numIn.N6;
    357. numOut.N7 = numIn.N7;
    358. numOut.N8 = numIn.N8;
    359. numOut.N9 = numIn.N9;
    360. }
    361. /// <summary>
    362. /// Set a number to value, which must be in range -185861411 .. 185861411
    363. /// </summary>
    364. static void Set(Long10 numOut, int numIn)
    365. {
    366. numOut.N0 = numIn;
    367. numOut.N1 = 0;
    368. numOut.N2 = 0;
    369. numOut.N3 = 0;
    370. numOut.N4 = 0;
    371. numOut.N5 = 0;
    372. numOut.N6 = 0;
    373. numOut.N7 = 0;
    374. numOut.N8 = 0;
    375. numOut.N9 = 0;
    376. }
    377. /* Add/subtract two numbers. The inputs must be in reduced form, and the
    378. * output isn't, so to do another addition or subtraction on the output,
    379. * first multiply it by one to reduce it. */
    380. static void Add(Long10 xy, Long10 x, Long10 y)
    381. {
    382. xy.N0 = x.N0 + y.N0;
    383. xy.N1 = x.N1 + y.N1;
    384. xy.N2 = x.N2 + y.N2;
    385. xy.N3 = x.N3 + y.N3;
    386. xy.N4 = x.N4 + y.N4;
    387. xy.N5 = x.N5 + y.N5;
    388. xy.N6 = x.N6 + y.N6;
    389. xy.N7 = x.N7 + y.N7;
    390. xy.N8 = x.N8 + y.N8;
    391. xy.N9 = x.N9 + y.N9;
    392. }
    393. static void Sub(Long10 xy, Long10 x, Long10 y)
    394. {
    395. xy.N0 = x.N0 - y.N0;
    396. xy.N1 = x.N1 - y.N1;
    397. xy.N2 = x.N2 - y.N2;
    398. xy.N3 = x.N3 - y.N3;
    399. xy.N4 = x.N4 - y.N4;
    400. xy.N5 = x.N5 - y.N5;
    401. xy.N6 = x.N6 - y.N6;
    402. xy.N7 = x.N7 - y.N7;
    403. xy.N8 = x.N8 - y.N8;
    404. xy.N9 = x.N9 - y.N9;
    405. }
    406. /// <summary>
    407. /// Multiply a number by a small integer in range -185861411 .. 185861411.
    408. /// The output is in reduced form, the input x need not be. x and xy may point
    409. /// to the same buffer.
    410. /// </summary>
    411. static void MulSmall(Long10 xy, Long10 x, long y)
    412. {
    413. long temp = (x.N8 * y);
    414. xy.N8 = (temp & ((1 << 26) - 1));
    415. temp = (temp >> 26) + (x.N9 * y);
    416. xy.N9 = (temp & ((1 << 25) - 1));
    417. temp = 19 * (temp >> 25) + (x.N0 * y);
    418. xy.N0 = (temp & ((1 << 26) - 1));
    419. temp = (temp >> 26) + (x.N1 * y);
    420. xy.N1 = (temp & ((1 << 25) - 1));
    421. temp = (temp >> 25) + (x.N2 * y);
    422. xy.N2 = (temp & ((1 << 26) - 1));
    423. temp = (temp >> 26) + (x.N3 * y);
    424. xy.N3 = (temp & ((1 << 25) - 1));
    425. temp = (temp >> 25) + (x.N4 * y);
    426. xy.N4 = (temp & ((1 << 26) - 1));
    427. temp = (temp >> 26) + (x.N5 * y);
    428. xy.N5 = (temp & ((1 << 25) - 1));
    429. temp = (temp >> 25) + (x.N6 * y);
    430. xy.N6 = (temp & ((1 << 26) - 1));
    431. temp = (temp >> 26) + (x.N7 * y);
    432. xy.N7 = (temp & ((1 << 25) - 1));
    433. temp = (temp >> 25) + xy.N8;
    434. xy.N8 = (temp & ((1 << 26) - 1));
    435. xy.N9 += (temp >> 26);
    436. }
    437. /// <summary>
    438. /// Multiply two numbers. The output is in reduced form, the inputs need not be.
    439. /// </summary>
    440. static void Multiply(Long10 xy, Long10 x, Long10 y)
    441. {
    442. /* sahn0:
    443. * Using local variables to avoid class access.
    444. * This seem to improve performance a bit...
    445. */
    446. long
    447. x0 = x.N0,
    448. x1 = x.N1,
    449. x2 = x.N2,
    450. x3 = x.N3,
    451. x4 = x.N4,
    452. x5 = x.N5,
    453. x6 = x.N6,
    454. x7 = x.N7,
    455. x8 = x.N8,
    456. x9 = x.N9;
    457. long
    458. y0 = y.N0,
    459. y1 = y.N1,
    460. y2 = y.N2,
    461. y3 = y.N3,
    462. y4 = y.N4,
    463. y5 = y.N5,
    464. y6 = y.N6,
    465. y7 = y.N7,
    466. y8 = y.N8,
    467. y9 = y.N9;
    468. long
    469. t = (x0*y8) + (x2*y6) + (x4*y4) + (x6*y2) +
    470. (x8*y0) + 2*((x1*y7) + (x3*y5) +
    471. (x5*y3) + (x7*y1)) + 38*
    472. (x9*y9);
    473. xy.N8 = (t & ((1 << 26) - 1));
    474. t = (t >> 26) + (x0 * y9) + (x1 * y8) + (x2 * y7) +
    475. (x3 * y6) + (x4 * y5) + (x5 * y4) +
    476. (x6 * y3) + (x7 * y2) + (x8 * y1) +
    477. (x9 * y0);
    478. xy.N9 = (t & ((1 << 25) - 1));
    479. t = (x0 * y0) + 19 * ((t >> 25) + (x2 * y8) + (x4 * y6)
    480. + (x6 * y4) + (x8 * y2)) + 38 *
    481. ((x1 * y9) + (x3 * y7) + (x5 * y5) +
    482. (x7 * y3) + (x9 * y1));
    483. xy.N0 = (t & ((1 << 26) - 1));
    484. t = (t >> 26) + (x0 * y1) + (x1 * y0) + 19 * ((x2 * y9)
    485. + (x3 * y8) + (x4 * y7) + (x5 * y6) +
    486. (x6 * y5) + (x7 * y4) + (x8 * y3) +
    487. (x9 * y2));
    488. xy.N1 = (t & ((1 << 25) - 1));
    489. t = (t >> 25) + (x0 * y2) + (x2 * y0) + 19 * ((x4 * y8)
    490. + (x6 * y6) + (x8 * y4)) + 2 * (x1 * y1)
    491. + 38 * ((x3 * y9) + (x5 * y7) +
    492. (x7 * y5) + (x9 * y3));
    493. xy.N2 = (t & ((1 << 26) - 1));
    494. t = (t >> 26) + (x0 * y3) + (x1 * y2) + (x2 * y1) +
    495. (x3 * y0) + 19 * ((x4 * y9) + (x5 * y8) +
    496. (x6 * y7) + (x7 * y6) +
    497. (x8 * y5) + (x9 * y4));
    498. xy.N3 = (t & ((1 << 25) - 1));
    499. t = (t >> 25) + (x0 * y4) + (x2 * y2) + (x4 * y0) + 19 *
    500. ((x6 * y8) + (x8 * y6)) + 2 * ((x1 * y3) +
    501. (x3 * y1)) + 38 *
    502. ((x5 * y9) + (x7 * y7) + (x9 * y5));
    503. xy.N4 = (t & ((1 << 26) - 1));
    504. t = (t >> 26) + (x0 * y5) + (x1 * y4) + (x2 * y3) +
    505. (x3 * y2) + (x4 * y1) + (x5 * y0) + 19 *
    506. ((x6 * y9) + (x7 * y8) + (x8 * y7) +
    507. (x9 * y6));
    508. xy.N5 = (t & ((1 << 25) - 1));
    509. t = (t >> 25) + (x0 * y6) + (x2 * y4) + (x4 * y2) +
    510. (x6 * y0) + 19 * (x8 * y8) + 2 * ((x1 * y5) +
    511. (x3 * y3) + (x5 * y1)) + 38 *
    512. ((x7 * y9) + (x9 * y7));
    513. xy.N6 = (t & ((1 << 26) - 1));
    514. t = (t >> 26) + (x0 * y7) + (x1 * y6) + (x2 * y5) +
    515. (x3 * y4) + (x4 * y3) + (x5 * y2) +
    516. (x6 * y1) + (x7 * y0) + 19 * ((x8 * y9) +
    517. (x9 * y8));
    518. xy.N7 = (t & ((1 << 25) - 1));
    519. t = (t >> 25) + xy.N8;
    520. xy.N8 = (t & ((1 << 26) - 1));
    521. xy.N9 += (t >> 26);
    522. }
    523. /// <summary>
    524. /// Square a number. Optimization of Multiply(x2, x, x)
    525. /// </summary>
    526. static void Square(Long10 xsqr, Long10 x)
    527. {
    528. long
    529. x0 = x.N0,
    530. x1 = x.N1,
    531. x2 = x.N2,
    532. x3 = x.N3,
    533. x4 = x.N4,
    534. x5 = x.N5,
    535. x6 = x.N6,
    536. x7 = x.N7,
    537. x8 = x.N8,
    538. x9 = x.N9;
    539. long t = (x4 * x4) + 2 * ((x0 * x8) + (x2 * x6)) + 38 *
    540. (x9 * x9) + 4 * ((x1 * x7) + (x3 * x5));
    541. xsqr.N8 = (t & ((1 << 26) - 1));
    542. t = (t >> 26) + 2 * ((x0 * x9) + (x1 * x8) + (x2 * x7) +
    543. (x3 * x6) + (x4 * x5));
    544. xsqr.N9 = (t & ((1 << 25) - 1));
    545. t = 19 * (t >> 25) + (x0 * x0) + 38 * ((x2 * x8) +
    546. (x4 * x6) + (x5 * x5)) + 76 * ((x1 * x9)
    547. + (x3 * x7));
    548. xsqr.N0 = (t & ((1 << 26) - 1));
    549. t = (t >> 26) + 2 * (x0 * x1) + 38 * ((x2 * x9) +
    550. (x3 * x8) + (x4 * x7) + (x5 * x6));
    551. xsqr.N1 = (t & ((1 << 25) - 1));
    552. t = (t >> 25) + 19 * (x6 * x6) + 2 * ((x0 * x2) +
    553. (x1 * x1)) + 38 * (x4 * x8) + 76 *
    554. ((x3 * x9) + (x5 * x7));
    555. xsqr.N2 = (t & ((1 << 26) - 1));
    556. t = (t >> 26) + 2 * ((x0 * x3) + (x1 * x2)) + 38 *
    557. ((x4 * x9) + (x5 * x8) + (x6 * x7));
    558. xsqr.N3 = (t & ((1 << 25) - 1));
    559. t = (t >> 25) + (x2 * x2) + 2 * (x0 * x4) + 38 *
    560. ((x6 * x8) + (x7 * x7)) + 4 * (x1 * x3) + 76 *
    561. (x5 * x9);
    562. xsqr.N4 = (t & ((1 << 26) - 1));
    563. t = (t >> 26) + 2 * ((x0 * x5) + (x1 * x4) + (x2 * x3))
    564. + 38 * ((x6 * x9) + (x7 * x8));
    565. xsqr.N5 = (t & ((1 << 25) - 1));
    566. t = (t >> 25) + 19 * (x8 * x8) + 2 * ((x0 * x6) +
    567. (x2 * x4) + (x3 * x3)) + 4 * (x1 * x5) +
    568. 76 * (x7 * x9);
    569. xsqr.N6 = (t & ((1 << 26) - 1));
    570. t = (t >> 26) + 2 * ((x0 * x7) + (x1 * x6) + (x2 * x5) +
    571. (x3 * x4)) + 38 * (x8 * x9);
    572. xsqr.N7 = (t & ((1 << 25) - 1));
    573. t = (t >> 25) + xsqr.N8;
    574. xsqr.N8 = (t & ((1 << 26) - 1));
    575. xsqr.N9 += (t >> 26);
    576. }
    577. /// <summary>
    578. /// Calculates a reciprocal. The output is in reduced form, the inputs need not
    579. /// be. Simply calculates y = x^(p-2) so it's not too fast. */
    580. /// When sqrtassist is true, it instead calculates y = x^((p-5)/8)
    581. /// </summary>
    582. static void Reciprocal(Long10 y, Long10 x, bool sqrtAssist)
    583. {
    584. Long10
    585. t0 = new Long10(),
    586. t1 = new Long10(),
    587. t2 = new Long10(),
    588. t3 = new Long10(),
    589. t4 = new Long10();
    590. int i;
    591. /* the chain for x^(2^255-21) is straight from djb's implementation */
    592. Square(t1, x); /* 2 == 2 * 1 */
    593. Square(t2, t1); /* 4 == 2 * 2 */
    594. Square(t0, t2); /* 8 == 2 * 4 */
    595. Multiply(t2, t0, x); /* 9 == 8 + 1 */
    596. Multiply(t0, t2, t1); /* 11 == 9 + 2 */
    597. Square(t1, t0); /* 22 == 2 * 11 */
    598. Multiply(t3, t1, t2); /* 31 == 22 + 9
    599. == 2^5 - 2^0 */
    600. Square(t1, t3); /* 2^6 - 2^1 */
    601. Square(t2, t1); /* 2^7 - 2^2 */
    602. Square(t1, t2); /* 2^8 - 2^3 */
    603. Square(t2, t1); /* 2^9 - 2^4 */
    604. Square(t1, t2); /* 2^10 - 2^5 */
    605. Multiply(t2, t1, t3); /* 2^10 - 2^0 */
    606. Square(t1, t2); /* 2^11 - 2^1 */
    607. Square(t3, t1); /* 2^12 - 2^2 */
    608. for (i = 1; i < 5; i++)
    609. {
    610. Square(t1, t3);
    611. Square(t3, t1);
    612. } /* t3 */ /* 2^20 - 2^10 */
    613. Multiply(t1, t3, t2); /* 2^20 - 2^0 */
    614. Square(t3, t1); /* 2^21 - 2^1 */
    615. Square(t4, t3); /* 2^22 - 2^2 */
    616. for (i = 1; i < 10; i++)
    617. {
    618. Square(t3, t4);
    619. Square(t4, t3);
    620. } /* t4 */ /* 2^40 - 2^20 */
    621. Multiply(t3, t4, t1); /* 2^40 - 2^0 */
    622. for (i = 0; i < 5; i++)
    623. {
    624. Square(t1, t3);
    625. Square(t3, t1);
    626. } /* t3 */ /* 2^50 - 2^10 */
    627. Multiply(t1, t3, t2); /* 2^50 - 2^0 */
    628. Square(t2, t1); /* 2^51 - 2^1 */
    629. Square(t3, t2); /* 2^52 - 2^2 */
    630. for (i = 1; i < 25; i++)
    631. {
    632. Square(t2, t3);
    633. Square(t3, t2);
    634. } /* t3 */ /* 2^100 - 2^50 */
    635. Multiply(t2, t3, t1); /* 2^100 - 2^0 */
    636. Square(t3, t2); /* 2^101 - 2^1 */
    637. Square(t4, t3); /* 2^102 - 2^2 */
    638. for (i = 1; i < 50; i++)
    639. {
    640. Square(t3, t4);
    641. Square(t4, t3);
    642. } /* t4 */ /* 2^200 - 2^100 */
    643. Multiply(t3, t4, t2); /* 2^200 - 2^0 */
    644. for (i = 0; i < 25; i++)
    645. {
    646. Square(t4, t3);
    647. Square(t3, t4);
    648. } /* t3 */ /* 2^250 - 2^50 */
    649. Multiply(t2, t3, t1); /* 2^250 - 2^0 */
    650. Square(t1, t2); /* 2^251 - 2^1 */
    651. Square(t2, t1); /* 2^252 - 2^2 */
    652. if (sqrtAssist)
    653. {
    654. Multiply(y, x, t2); /* 2^252 - 3 */
    655. }
    656. else
    657. {
    658. Square(t1, t2); /* 2^253 - 2^3 */
    659. Square(t2, t1); /* 2^254 - 2^4 */
    660. Square(t1, t2); /* 2^255 - 2^5 */
    661. Multiply(y, t1, t0); /* 2^255 - 21 */
    662. }
    663. }
    664. /// <summary>
    665. /// Checks if x is "negative", requires reduced input
    666. /// </summary>
    667. /// <param name="x">must be reduced input</param>
    668. static int IsNegative(Long10 x)
    669. {
    670. return (int)(((IsOverflow(x) | (x.N9 < 0)) ? 1 : 0) ^ (x.N0 & 1));
    671. }
    672. /********************* Elliptic curve *********************/
    673. /* y^2 = x^3 + 486662 x^2 + x over GF(2^255-19) */
    674. /* t1 = ax + az
    675. * t2 = ax - az */
    676. static void MontyPrepare(Long10 t1, Long10 t2, Long10 ax, Long10 az)
    677. {
    678. Add(t1, ax, az);
    679. Sub(t2, ax, az);
    680. }
    681. /* A = P + Q where
    682. * X(A) = ax/az
    683. * X(P) = (t1+t2)/(t1-t2)
    684. * X(Q) = (t3+t4)/(t3-t4)
    685. * X(P-Q) = dx
    686. * clobbers t1 and t2, preserves t3 and t4 */
    687. static void MontyAdd(Long10 t1, Long10 t2, Long10 t3, Long10 t4, Long10 ax, Long10 az, Long10 dx)
    688. {
    689. Multiply(ax, t2, t3);
    690. Multiply(az, t1, t4);
    691. Add(t1, ax, az);
    692. Sub(t2, ax, az);
    693. Square(ax, t1);
    694. Square(t1, t2);
    695. Multiply(az, t1, dx);
    696. }
    697. /* B = 2 * Q where
    698. * X(B) = bx/bz
    699. * X(Q) = (t3+t4)/(t3-t4)
    700. * clobbers t1 and t2, preserves t3 and t4 */
    701. static void MontyDouble(Long10 t1, Long10 t2, Long10 t3, Long10 t4, Long10 bx, Long10 bz)
    702. {
    703. Square(t1, t3);
    704. Square(t2, t4);
    705. Multiply(bx, t1, t2);
    706. Sub(t2, t1, t2);
    707. MulSmall(bz, t2, 121665);
    708. Add(t1, t1, bz);
    709. Multiply(bz, t1, t2);
    710. }
    711. /// <summary>
    712. /// Y^2 = X^3 + 486662 X^2 + X
    713. /// </summary>
    714. /// <param name="y2">output</param>
    715. /// <param name="x">X</param>
    716. /// <param name="temp">temporary</param>
    717. static void CurveEquationInline(Long10 y2, Long10 x, Long10 temp)
    718. {
    719. Square(temp, x);
    720. MulSmall(y2, x, 486662);
    721. Add(temp, temp, y2);
    722. temp.N0++;
    723. Multiply(y2, temp, x);
    724. }
    725. /// <summary>
    726. /// P = kG and s = sign(P)/k
    727. /// </summary>
    728. static void Core(byte[] publicKey, byte[] signingKey, byte[] privateKey, byte[] peerPublicKey)
    729. {
    730. if (publicKey == null) throw new ArgumentNullException("publicKey");
    731. if (publicKey.Length != 32) throw new ArgumentException(String.Format("publicKey must be 32 bytes long (but was {0} bytes long)", publicKey.Length), "publicKey");
    732. if (signingKey != null && signingKey.Length != 32) throw new ArgumentException(String.Format("signingKey must be null or 32 bytes long (but was {0} bytes long)", signingKey.Length), "signingKey");
    733. if (privateKey == null) throw new ArgumentNullException("privateKey");
    734. if (privateKey.Length != 32) throw new ArgumentException(String.Format("privateKey must be 32 bytes long (but was {0} bytes long)", privateKey.Length), "privateKey");
    735. if (peerPublicKey != null && peerPublicKey.Length != 32) throw new ArgumentException(String.Format("peerPublicKey must be null or 32 bytes long (but was {0} bytes long)", peerPublicKey.Length), "peerPublicKey");
    736. Long10
    737. dx = new Long10(),
    738. t1 = new Long10(),
    739. t2 = new Long10(),
    740. t3 = new Long10(),
    741. t4 = new Long10();
    742. Long10[]
    743. x = { new Long10(), new Long10() },
    744. z = { new Long10(), new Long10() };
    745. /* unpack the base */
    746. if (peerPublicKey != null)
    747. Unpack(dx, peerPublicKey);
    748. else
    749. Set(dx, 9);
    750. /* 0G = point-at-infinity */
    751. Set(x[0], 1);
    752. Set(z[0], 0);
    753. /* 1G = G */
    754. Copy(x[1], dx);
    755. Set(z[1], 1);
    756. for (int i = 32; i-- != 0; )
    757. {
    758. for (int j = 8; j-- != 0; )
    759. {
    760. /* swap arguments depending on bit */
    761. int bit1 = (privateKey[i] & 0xFF) >> j & 1;
    762. int bit0 = ~(privateKey[i] & 0xFF) >> j & 1;
    763. Long10 ax = x[bit0];
    764. Long10 az = z[bit0];
    765. Long10 bx = x[bit1];
    766. Long10 bz = z[bit1];
    767. /* a' = a + b */
    768. /* b' = 2 b */
    769. MontyPrepare(t1, t2, ax, az);
    770. MontyPrepare(t3, t4, bx, bz);
    771. MontyAdd(t1, t2, t3, t4, ax, az, dx);
    772. MontyDouble(t1, t2, t3, t4, bx, bz);
    773. }
    774. }
    775. Reciprocal(t1, z[0], false);
    776. Multiply(dx, x[0], t1);
    777. Pack(dx, publicKey);
    778. /* calculate s such that s abs(P) = G .. assumes G is std base point */
    779. if (signingKey != null)
    780. {
    781. CurveEquationInline(t1, dx, t2); /* t1 = Py^2 */
    782. Reciprocal(t3, z[1], false); /* where Q=P+G ... */
    783. Multiply(t2, x[1], t3); /* t2 = Qx */
    784. Add(t2, t2, dx); /* t2 = Qx + Px */
    785. t2.N0 += 9 + 486662; /* t2 = Qx + Px + Gx + 486662 */
    786. dx.N0 -= 9; /* dx = Px - Gx */
    787. Square(t3, dx); /* t3 = (Px - Gx)^2 */
    788. Multiply(dx, t2, t3); /* dx = t2 (Px - Gx)^2 */
    789. Sub(dx, dx, t1); /* dx = t2 (Px - Gx)^2 - Py^2 */
    790. dx.N0 -= 39420360; /* dx = t2 (Px - Gx)^2 - Py^2 - Gy^2 */
    791. Multiply(t1, dx, BaseR2Y); /* t1 = -Py */
    792. if (IsNegative(t1) != 0) /* sign is 1, so just copy */
    793. Copy32(privateKey, signingKey);
    794. else /* sign is -1, so negate */
    795. MultiplyArraySmall(signingKey, OrderTimes8, 0, privateKey, 32, -1);
    796. /* reduce s mod q
    797. * (is this needed? do it just in case, it's fast anyway) */
    798. //divmod((dstptr) t1, s, 32, order25519, 32);
    799. /* take reciprocal of s mod q */
    800. var temp1 = new byte[32];
    801. var temp2 = new byte[64];
    802. var temp3 = new byte[64];
    803. Copy32(Order, temp1);
    804. Copy32(Egcd32(temp2, temp3, signingKey, temp1), signingKey);
    805. if ((signingKey[31] & 0x80) != 0)
    806. MultiplyArraySmall(signingKey, signingKey, 0, Order, 32, 1);
    807. }
    808. }
    809. /// <summary>
    810. /// Smallest multiple of the order that's >= 2^255
    811. /// </summary>
    812. static readonly byte[] OrderTimes8 =
    813. {
    814. 104, 159, 174, 231,
    815. 210, 24, 147, 192,
    816. 178, 230, 188, 23,
    817. 245, 206, 247, 166,
    818. 0, 0, 0, 0,
    819. 0, 0, 0, 0,
    820. 0, 0, 0, 0,
    821. 0, 0, 0, 128
    822. };
    823. /// <summary>
    824. /// Constant 1/(2Gy)
    825. /// </summary>
    826. static readonly Long10 BaseR2Y = new Long10(
    827. 5744, 8160848, 4790893, 13779497, 35730846,
    828. 12541209, 49101323, 30047407, 40071253, 6226132
    829. );
    830. }
    831. }

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „evolver“ ()

    Alles Gute zum neuen Jahr

    Ich glaube so muss es heissen.

    C#-Quellcode

    1. static int GetNumSize(byte[] num, int maxSize)
    2. {
    3. while (maxSize-- != 0 && num[maxSize] == 0) ;
    4. return maxSize + 1;
    5. }


    VB.NET-Quellcode

    1. Private Shared Function GetNumSize(num As Byte(), maxSize As Integer) As Integer
    2. maxSize -= 1
    3. While Not maxSize < 0 AndAlso num(maxSize) = 0
    4. maxSize -= 1
    5. End While
    6. Return maxSize + 1
    7. End Function

    evolver schrieb:

    hallo ErfinderDesRades,
    es ist schon recht komisch, scheinbar funzen die externen Links bei dir nicht?
    Keine Ahnung, ich klickse da nicht drauf.
    Ich mag nicht durch die Weltgeschichte surfen, und da überall zustimmen müssen, dass die Cookies verwenden, und tracking-Bits von google und und und.
    Du möchtest hier im Forum was zeigen, dann tu das auch hier im Forum.
    Und mit "entsprechendem" Code meinte ich auch nicht allen Code, sondern nur den entsprechenden Code, nämlich den vom Vorpost - das waren ja nur 10 vb.net-Zeilen.

    Ansonsten: Wenn du längere Listings einfügen willst (so ab 50 zeilen), verwende bitte den Spoiler-Tag des Forums.



    Die Methode täte ich so formulieren:

    VB.NET-Quellcode

    1. Private Shared Function GetNumSize(num As Byte(), maxSize As Integer) As Integer
    2. For i = maxSize - 1 To 1 Step -1
    3. If num(i) <> 0 Then Return i
    4. Next
    5. Return 0
    6. End Function
    Oder mit den Möglichkeiten, die .net eben hat:

    VB.NET-Quellcode

    1. Private Shared Function GetNumSize(num As Byte(), maxSize As Integer) As Integer
    2. Return Array.FindLastIndex(num, Function(n) n <> 0)
    3. End Function

    (Fast-)Vollzitat des direkten Vorposts an dieser Stelle entfernt ~VaporiZed

    Ah. Ja, das mit dem Cookie und Trackingzeugs kann ich schon verstehen. Ich sympathisiere auch eher mit der Anonymität, ich dachte jedoch GitHub wäre ok. Nun gut, dann weiß ich jetzt bescheid!
    Zurück zum Code:
    Dein code funzt. Jedoch kommt nach wie vor (leider) der falsche SignKey heraus. Nun jedoch habe ich keinen Anhaltspunkt mehr wo noch was falsch sein könnte denn es läuft ja durch ?(
    Vllt hilft noch der Aufruf:

    VB.NET-Quellcode

    1. Public Shared Function keygen( k() As Byte)As Byte()()
    2. Dim P(31) As Byte
    3. Dim s(31) As Byte
    4. RefCurve25519.ClampPrivateKeyInline(k)
    5. RefCurve25519.Core(P, s, k, Nothing)
    6. Return {P, s, k}
    7. End Function


    Diese Funktion wiederum wird von nachfolgender aufgerufen:

    VB.NET-Quellcode

    1. Function generateMasterKeys(ByVal passPhrase As String) As List(Of String)
    2. Dim cSHA256 As System.Security.Cryptography.SHA256 = System.Security.Cryptography.SHA256Managed.Create()
    3. Dim hashPhrase As List(Of Byte) = cSHA256.ComputeHash(System.Text.Encoding.UTF8.GetBytes(passPhrase).ToArray).ToList
    4. Dim hashPhraseHEX As String = ByteAry2HEX(hashPhrase.ToArray)
    5. Dim keys()() As Byte = ECKCDSA.keygen(hashPhrase.ToArray)
    6. Dim PubKeyByteList As List(Of Byte) = New List(Of Byte)
    7. For Each x In keys(0)
    8. PubKeyByteList.Add(x)
    9. Next
    10. Dim SignKeyByteList As List(Of Byte) = New List(Of Byte)
    11. For Each x In keys(1)
    12. SignKeyByteList.Add(x)
    13. Next
    14. Dim AgreePrivKeyByteList As List(Of Byte) = New List(Of Byte)
    15. For Each x In keys(2)
    16. AgreePrivKeyByteList.Add(x)
    17. Next
    18. Dim PubKey As String = ByteAry2HEX(PubKeyByteList.ToArray)
    19. Dim SignKey As String = ByteAry2HEX(cSHA256.ComputeHash(SignKeyByteList.ToArray))
    20. Dim AgreePrivKey As String = ByteAry2HEX(AgreePrivKeyByteList.ToArray)
    21. Dim KeyList As List(Of String) = New List(Of String)({PubKey, SignKey, AgreePrivKey})
    22. Return KeyList
    23. End Function


    und diese Funktion bekommt den String Parameter-Wert "test" und sollte folgendes liefern:

    zum einen den publicKey :"d9d5c57971eefb085e3abaf7a5a4a6cdb8185f30105583cdb09ad8f61886ec65"
    zum anderen den signPrivateKey: "2a4a4b632b1dc4533534d37e3cbebef02570b2d0584e9cd4e632204f5855670b"
    und zu letzt den agreementPrivateKey: "9886d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a48"

    der PublicKey und der agreementPrivateKey wird richtig zurückgegeben, nur eben der signKey nicht

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „VaporiZed“ ()

    Die beiden Methoden haben keinen Datentyp (das ist in c# garnet möglich).
    Dringend empfohlen: Visual Studio - Empfohlene Einstellungen
    Vermutlich findest du dann mit Strict On auch noch weitere Übersetzungs-Fehler.
    Evtl. sollteste auch weitere Übersetzungs-Tools ausprobieren, ich kenn das so, dass Tools die c#-Typisierung korrekt übersetzen.

    Wirklich gut voran kommt man bei so Übersetzungen, wenn man immer beides vor Augen hat:
    den original c#-Code und den entsprechenden, automatisch übersetzten vb.net-Code, der aber vlt. Fehler hat.

    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „ErfinderDesRades“ ()

    Vollzitat des direkten Vorposts an dieser Stelle entfernt ~VaporiZed

    Oh mist, du hast recht! Normalerweise definiere ich immer einen rückgabetyp... aber ja, ich habe es nun umgeändert. Das Ergebnis ist jedoch immer noch das gleiche. Kann jmd vllt diese Keys bestätigen, die ich gepostet habe?

    evolver schrieb:



    und diese Funktion bekommt den String Parameter-Wert "test" und sollte folgendes liefern:

    zum einen den publicKey :"d9d5c57971eefb085e3abaf7a5a4a6cdb8185f30105583cdb09ad8f61886ec65"
    zum anderen den signPrivateKey: "2a4a4b632b1dc4533534d37e3cbebef02570b2d0584e9cd4e632204f5855670b"
    und zu letzt den agreementPrivateKey: "9886d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a48"

    der PublicKey und der agreementPrivateKey wird richtig zurückgegeben, nur eben der signKey nicht


    ich habe hier mal meinen Fortschritt in VB.NET:
    Spoiler anzeigen

    Quellcode

    1. ' Ported parts from Java to C# and refactored by Hans Wolff, 17/09/2013
    2. ' Ported from C to Java by Dmitry Skiba [sahn0], 23/02/08.
    3. ' Original: http://code.google.com/p/curve25519-java/
    4. '
    5. ' Generic 64-bit integer implementation of Curve25519 ECDH
    6. ' Written by Matthijs van Duin, 200608242056
    7. ' Public domain.
    8. '
    9. ' Based on work by Daniel J Bernstein, http://cr.yp.to/ecdh.html
    10. '
    11. Option Strict On
    12. Imports Microsoft.VisualBasic
    13. Imports System
    14. Imports System.Security.Cryptography
    15. Namespace Elliptic
    16. Public Class RefCurve25519
    17. ' key size
    18. Public Const KeySize As Integer = 32
    19. ' group order (a prime near 2^252+2^124)
    20. Public Shared ReadOnly 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}
    21. #Region "******* KEY AGREEMENT ********"
    22. ''' <summary>
    23. ''' Private key clamping (inline, for performance)
    24. ''' </summary>
    25. ''' <param name="key">[out] 32 random bytes</param>
    26. Public Shared Sub ClampPrivateKeyInline(ByVal key As Byte())
    27. If key Is Nothing Then Throw New ArgumentNullException("key")
    28. If key.Length <> 32 Then Throw New ArgumentException(String.Format("key must be 32 bytes long (but was {0} bytes long)", key.Length))
    29. key(31) = CByte(key(31) And &H7F)
    30. key(31) = CByte(key(31) Or &H40)
    31. key(0) = CByte(key(0) And &HF8)
    32. End Sub
    33. ''' <summary>
    34. ''' Private key clamping
    35. ''' </summary>
    36. ''' <param name="rawKey">[out] 32 random bytes</param>
    37. Public Shared Function ClampPrivateKey(ByVal rawKey As Byte()) As Byte()
    38. If rawKey Is Nothing Then Throw New ArgumentNullException("rawKey")
    39. If rawKey.Length <> 32 Then Throw New ArgumentException(String.Format("rawKey must be 32 bytes long (but was {0} bytes long)", rawKey.Length), "rawKey")
    40. Dim res = New Byte(31) {}
    41. Array.Copy(rawKey, res, 32)
    42. res(31) = CByte(res(31) And &H7F)
    43. res(31) = CByte(res(31) Or &H40)
    44. res(0) = CByte(res(0) And &HF8)
    45. Return res
    46. End Function
    47. ''' <summary>
    48. ''' Creates a random private key
    49. ''' </summary>
    50. ''' <returns>32 random bytes that are clamped to a suitable private key</returns>
    51. Public Shared Function CreateRandomPrivateKey() As Byte()
    52. Dim privateKey = New Byte(31) {}
    53. RandomNumberGenerator.Create().GetBytes(privateKey)
    54. ClampPrivateKeyInline(privateKey)
    55. Return privateKey
    56. End Function
    57. ''' <summary>
    58. ''' Key-pair generation (inline, for performance)
    59. ''' </summary>
    60. ''' <param name="publicKey">[out] public key</param>
    61. ''' <param name="signingKey">[out] signing key (ignored if NULL)</param>
    62. ''' <param name="privateKey">[out] private key</param>
    63. ''' <remarks>WARNING: if signingKey is not NULL, this function has data-dependent timing</remarks>
    64. Public Shared Sub KeyGenInline(ByVal publicKey As Byte(), ByVal signingKey As Byte(), ByVal privateKey As Byte())
    65. If publicKey Is Nothing Then Throw New ArgumentNullException("publicKey")
    66. If publicKey.Length <> 32 Then Throw New ArgumentException(String.Format("publicKey must be 32 bytes long (but was {0} bytes long)", publicKey.Length), "publicKey")
    67. If signingKey Is Nothing Then Throw New ArgumentNullException("signingKey")
    68. If signingKey.Length <> 32 Then Throw New ArgumentException(String.Format("signingKey must be 32 bytes long (but was {0} bytes long)", signingKey.Length), "signingKey")
    69. If privateKey Is Nothing Then Throw New ArgumentNullException("privateKey")
    70. If privateKey.Length <> 32 Then Throw New ArgumentException(String.Format("privateKey must be 32 bytes long (but was {0} bytes long)", privateKey.Length), "privateKey")
    71. RandomNumberGenerator.Create().GetBytes(privateKey)
    72. ClampPrivateKeyInline(privateKey)
    73. Core(publicKey, signingKey, privateKey, Nothing)
    74. End Sub
    75. ''' <summary>
    76. ''' Generates the public key out of the clamped private key
    77. ''' </summary>
    78. ''' <param name="privateKey">private key (must use ClampPrivateKey first!)</param>
    79. Public Shared Function GetPublicKey(ByVal privateKey As Byte()) As Byte()
    80. Dim publicKey = New Byte(31) {}
    81. Core(publicKey, Nothing, privateKey, Nothing)
    82. Return publicKey
    83. End Function
    84. ''' <summary>
    85. ''' Generates signing key out of the clamped private key
    86. ''' </summary>
    87. ''' <param name="privateKey">private key (must use ClampPrivateKey first!)</param>
    88. Public Shared Function GetSigningKey(ByRef publicKey As Byte(), ByRef signingKey As Byte(), ByVal privateKey As Byte()) As Byte()
    89. 'Dim signingKey = New Byte(31) {}
    90. 'Dim publicKey = New Byte(31) {}
    91. Core(publicKey, signingKey, privateKey, Nothing)
    92. Return signingKey
    93. End Function
    94. ''' <summary>
    95. ''' Key agreement
    96. ''' </summary>
    97. ''' <param name="privateKey">[in] your private key for key agreement</param>
    98. ''' <param name="peerPublicKey">[in] peer's public key</param>
    99. ''' <returns>shared secret (needs hashing before use)</returns>
    100. Public Shared Function GetSharedSecret(ByVal privateKey As Byte(), ByVal peerPublicKey As Byte()) As Byte()
    101. Dim sharedSecret = New Byte(31) {}
    102. Core(sharedSecret, Nothing, privateKey, peerPublicKey)
    103. Return sharedSecret
    104. End Function
    105. ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
    106. #End Region
    107. ' sahn0:
    108. ' Using this class instead of long[10] to avoid bounds checks.
    109. Public NotInheritable Class Long10
    110. Public Sub New()
    111. End Sub
    112. Public Sub New(ByVal n0 As Long, ByVal n1 As Long, ByVal n2 As Long, ByVal n3 As Long, ByVal n4 As Long, ByVal n5 As Long, ByVal n6 As Long, ByVal n7 As Long, ByVal n8 As Long, ByVal n9 As Long)
    113. Me.N0 = n0
    114. Me.N1 = n1
    115. Me.N2 = n2
    116. Me.N3 = n3
    117. Me.N4 = n4
    118. Me.N5 = n5
    119. Me.N6 = n6
    120. Me.N7 = n7
    121. Me.N8 = n8
    122. Me.N9 = n9
    123. End Sub
    124. Public N0, N1, N2, N3, N4, N5, N6, N7, N8, N9 As Long
    125. End Class
    126. ' ******************* radix 2^8 math ********************
    127. Public Shared Sub Copy32(ByRef source As Byte(), ByRef destination As Byte())
    128. Array.Copy(source, 0, destination, 0, 32)
    129. End Sub
    130. ' p[m..n+m-1] = q[m..n+m-1] + z * x
    131. ' n is the size of x
    132. ' n+m is the size of p and q
    133. Public Shared Function MultiplyArraySmall(ByRef p As Byte(), ByRef q As Byte(), m As Integer, x As Byte(), n As Integer, z As Integer) As Integer
    134. n -= 1
    135. Dim v As Integer = 0
    136. For i As Integer = 0 To n - 1
    137. Dim temp = q(i + m)
    138. Dim temp1 = x(i)
    139. v += (temp And &HFF) + z * (temp1 And &HFF)
    140. p(i + m) = BitConverter.GetBytes(v)(0)
    141. v >>= 8
    142. Next
    143. Return v
    144. #Region "Tests"
    145. 'Dim v As Integer = 0
    146. 'Dim i As Integer = 0
    147. 'While i < n
    148. ' v += (q(i + m) And &HFF) + z * (x(i) And &HFF)
    149. ' p(i + m) = CByte(v)
    150. ' v >>= 8
    151. ' Threading.Interlocked.Increment(i)
    152. 'End While
    153. 'Return v
    154. #End Region
    155. End Function
    156. ' p += x * y * z where z is a small integer
    157. ' x is size 32, y is size t, p is size 32+t
    158. ' y is allowed to overlap with p+32 if you don't care about the upper half
    159. Public Shared Sub MultiplyArray32(ByRef p As Byte(), ByRef x As Byte(), ByRef y As Byte(), ByRef t As Integer, ByRef z As Integer)
    160. Const n As Integer = 31
    161. Dim w As Integer = 0
    162. Dim i As Integer = 0
    163. While i < t
    164. Dim zy As Integer = z * (y(i) And &HFF)
    165. w += MultiplyArraySmall(p, p, i, x, n, zy) + (p(i + n) And &HFF) + zy * (x(n) And &HFF)
    166. p(i + n) = BitConverter.GetBytes(w)(0)
    167. w >>= 8
    168. i += 1
    169. End While
    170. p(i + n) = BitConverter.GetBytes(w + (p(i + n) And &HFF))(0)
    171. End Sub
    172. ' divide r (size n) by d (size t), returning quotient q and remainder r
    173. ' quotient is size n-t+1, remainder is size t
    174. ' requires t > 0 && d[t-1] != 0
    175. ' requires that r[-1] and d[-1] are valid memory locations
    176. ' q may overlap with r+t
    177. Public Shared Sub DivMod(ByRef q As Byte(), ByRef r As Byte(), n As Integer, d As Byte(), t As Integer)
    178. Dim rn As Integer = 0
    179. Dim dt As Integer = (d(t - 1) And &HFF) << 8
    180. If t > 1 Then
    181. dt = dt Or d(t - 2) And &HFF
    182. End If
    183. While n >= t
    184. n -= 1
    185. #Region "Debug/Test1"
    186. 'If n = -1 Then
    187. 'Exit Sub
    188. 'End If
    189. #End Region
    190. Dim z As Integer = (rn << 16) Or ((r(n) And &HFF) << 8)
    191. If n > 0 Then
    192. z = z Or r(n) And &HFF
    193. End If
    194. z = CInt(z / dt)
    195. rn += MultiplyArraySmall(r, r, n - t + 1, d, t, -z)
    196. Dim temp = CByte(z + rn And &HFF)
    197. Dim temp1 = n - t + 1
    198. #Region "Debug/Test2"
    199. 'If q.Length - 1 < temp1 Then
    200. 'ReDim Preserve q(temp1)
    201. 'End If
    202. #End Region
    203. q(temp1) = temp ' rn is 0 or -1 (underflow)
    204. MultiplyArraySmall(r, r, n - t + 1, d, t, -rn)
    205. rn = r(n) And &HFF
    206. r(n) = 0
    207. End While
    208. r(t - 1) = CByte(rn)
    209. End Sub
    210. Private Shared Function GetNumSize(ByVal num As Byte(), ByVal maxSize As Integer) As Integer
    211. For i = maxSize - 1 To 1 Step -1
    212. If num(i) <> 0 Then Return i
    213. Next
    214. Return 0
    215. #Region "Tests"
    216. 'maxSize -= 1
    217. 'While Not maxSize < 0 AndAlso num(maxSize) = 0
    218. ' maxSize -= 1
    219. 'End While
    220. 'Return maxSize + 1
    221. 'Dim i As Integer = maxSize
    222. 'While i >= 0
    223. ' If num(i) = 0 Then
    224. ' Return i + 1
    225. ' End If
    226. ' i += 1
    227. 'End While
    228. 'Return 0
    229. 'Dim NUnum As List(Of Byte) = New List(Of Byte)
    230. 'Dim NuMax As Integer = num.Length
    231. 'If NuMax > maxSize Then
    232. ' NuMax = maxSize
    233. 'End If
    234. 'For i As Integer = 0 To NuMax - 1
    235. ' If num(i) = 0 Then
    236. ' Return i
    237. ' End If
    238. 'Next
    239. 'Return maxSize
    240. 'Dim NUnum As List(Of Byte) = New List(Of Byte)
    241. 'Dim NuMax As Integer = num.Length - 1
    242. 'If NuMax > maxSize Then
    243. ' NuMax = maxSize
    244. 'End If
    245. 'For i As Integer = NuMax To 0 Step -1
    246. ' If num(i) = 0 Then
    247. ' Else
    248. ' Return i + 1
    249. ' End If
    250. 'Next
    251. 'Return maxSize
    252. #End Region
    253. End Function
    254. ''' <summary>
    255. ''' Returns x if a contains the gcd, y if b.
    256. ''' </summary>
    257. ''' <param name="x">x and y must have 64 bytes space for temporary use.</param>
    258. ''' <param name="y">x and y must have 64 bytes space for temporary use.</param>
    259. ''' <param name="a">requires that a[-1] and b[-1] are valid memory locations</param>
    260. ''' <param name="b">requires that a[-1] and b[-1] are valid memory locations</param>
    261. ''' <returns>Also, the returned buffer contains the inverse of a mod b as 32-byte signed.</returns>
    262. Private Shared Function Egcd32(ByRef x As Byte(), ByRef y As Byte(), ByRef a As Byte(), ByRef b As Byte()) As Byte()
    263. Dim bn As Integer = 32
    264. Dim i As Integer
    265. For i = 0 To 32 - 1
    266. x(i) = y(i)
    267. y(i) = 0
    268. Next
    269. x(0) = 1
    270. Dim an As Integer = GetNumSize(a, 31)
    271. If an = 0 Then Return y ' division by zero
    272. Dim temp = New Byte(32) {}
    273. While True
    274. Dim qn As Integer = bn - an + 1
    275. DivMod(temp, b, bn, a, an)
    276. bn = GetNumSize(b, bn)
    277. If bn <= 0 Then
    278. Return x
    279. End If
    280. MultiplyArray32(y, x, temp, qn, -1)
    281. qn = an - bn + 1
    282. DivMod(temp, a, an, b, bn)
    283. an = GetNumSize(a, an)
    284. If an <= 0 Then
    285. Return y
    286. End If
    287. MultiplyArray32(x, y, temp, qn, -1)
    288. End While
    289. 'TODO: Egcd32 Else Return
    290. End Function
    291. ' ******************* radix 2^25.5 GF(2^255-19) math ********************
    292. Private Const P25 As Integer = 33554431 ' (1 << 25) - 1
    293. Private Const P26 As Integer = 67108863 ' (1 << 26) - 1
    294. ' Convert to internal format from little-endian byte format
    295. Public Shared Sub Unpack(ByRef x As Long10, ByRef m As Byte())
    296. x.N0 = m(0) And &HFF Or (m(1) And &HFF) << 8 Or (m(2) And &HFF) << 16 Or (m(3) And &HFF And 3) << 24
    297. x.N1 = (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
    298. x.N2 = (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
    299. x.N3 = (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
    300. x.N4 = (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
    301. x.N5 = m(16) And &HFF Or (m(17) And &HFF) << 8 Or (m(18) And &HFF) << 16 Or (m(19) And &HFF And 1) << 24
    302. x.N6 = (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
    303. x.N7 = (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
    304. x.N8 = (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
    305. x.N9 = (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
    306. End Sub
    307. ''' <summary>
    308. ''' Check if reduced-form input >= 2^255-19
    309. ''' </summary>
    310. Private Shared Function IsOverflow(ByVal x As Long10) As Boolean
    311. Return x.N0 > P26 - 19 And (x.N1 And x.N3 And x.N5 And x.N7 And x.N9) = P25 And (x.N2 And x.N4 And x.N6 And x.N8) = P26 OrElse x.N9 > P25
    312. End Function
    313. ' Convert from internal format to little-endian byte format. The
    314. ' number must be in a reduced form which is output by the following ops:
    315. ' unpack, mul, sqr
    316. ' set -- if input in range 0 .. P25
    317. ' If you're unsure if the number is reduced, first multiply it by 1.
    318. Private Shared Sub Pack(ByRef x As Long10, ByRef m As Byte())
    319. Dim ld As Integer = If(IsOverflow(x), 1, 0) - If(x.N9 < 0, 1, 0)
    320. Dim ud As Integer = ld * -(P25 + 1)
    321. ld *= 19
    322. Dim t As Long = ld + x.N0 + (x.N1 << 26)
    323. Dim bAry() As Byte = BitConverter.GetBytes(t)
    324. m(0) = bAry(0) ' CByte(t)
    325. m(1) = bAry(1) ' CByte(t >> 8)
    326. m(2) = bAry(2) ' CByte(t >> 16)
    327. m(3) = bAry(3) ' CByte(t >> 24)
    328. t = (t >> 32) + (x.N2 << 19)
    329. bAry = BitConverter.GetBytes(t)
    330. m(4) = bAry(0) ' CByte(t)
    331. m(5) = bAry(1) ' CByte(t >> 8)
    332. m(6) = bAry(2) ' CByte(t >> 16)
    333. m(7) = bAry(3) ' CByte(t >> 24)
    334. t = (t >> 32) + (x.N3 << 13)
    335. bAry = BitConverter.GetBytes(t)
    336. m(8) = bAry(0) ' CByte(t)
    337. m(9) = bAry(1) ' CByte(t >> 8)
    338. m(10) = bAry(2) ' CByte(t >> 16)
    339. m(11) = bAry(3) ' CByte(t >> 24)
    340. t = (t >> 32) + (x.N4 << 6)
    341. bAry = BitConverter.GetBytes(t)
    342. m(12) = bAry(0) ' CByte(t)
    343. m(13) = bAry(1) ' CByte(t >> 8)
    344. m(14) = bAry(2) ' CByte(t >> 16)
    345. m(15) = bAry(3) ' CByte(t >> 24)
    346. t = (t >> 32) + x.N5 + (x.N6 << 25)
    347. bAry = BitConverter.GetBytes(t)
    348. m(16) = bAry(0) ' CByte(t)
    349. m(17) = bAry(1) ' CByte(t >> 8)
    350. m(18) = bAry(2) ' CByte(t >> 16)
    351. m(19) = bAry(3) ' CByte(t >> 24)
    352. t = (t >> 32) + (x.N7 << 19)
    353. bAry = BitConverter.GetBytes(t)
    354. m(20) = bAry(0) ' CByte(t)
    355. m(21) = bAry(1) ' CByte(t >> 8)
    356. m(22) = bAry(2) ' CByte(t >> 16)
    357. m(23) = bAry(3) ' CByte(t >> 24)
    358. t = (t >> 32) + (x.N8 << 12)
    359. bAry = BitConverter.GetBytes(t)
    360. m(24) = bAry(0) ' CByte(t)
    361. m(25) = bAry(1) ' CByte(t >> 8)
    362. m(26) = bAry(2) ' CByte(t >> 16)
    363. m(27) = bAry(3) ' CByte(t >> 24)
    364. t = (t >> 32) + (x.N9 + ud << 6)
    365. bAry = BitConverter.GetBytes(t)
    366. m(28) = bAry(0) ' CByte(t)
    367. m(29) = bAry(1) ' CByte(t >> 8)
    368. m(30) = bAry(2) ' CByte(t >> 16)
    369. m(31) = bAry(3) ' CByte(t >> 24)
    370. End Sub
    371. ''' <summary>
    372. ''' Copy a number
    373. ''' </summary>
    374. Public Shared Sub Copy(ByRef numOut As Long10, ByRef numIn As Long10)
    375. numOut.N0 = numIn.N0
    376. numOut.N1 = numIn.N1
    377. numOut.N2 = numIn.N2
    378. numOut.N3 = numIn.N3
    379. numOut.N4 = numIn.N4
    380. numOut.N5 = numIn.N5
    381. numOut.N6 = numIn.N6
    382. numOut.N7 = numIn.N7
    383. numOut.N8 = numIn.N8
    384. numOut.N9 = numIn.N9
    385. End Sub
    386. ''' <summary>
    387. ''' Set a number to value, which must be in range -185861411 .. 185861411
    388. ''' </summary>
    389. Public Shared Sub [Set](ByRef numOut As Long10, ByRef numIn As Integer)
    390. numOut.N0 = numIn
    391. numOut.N1 = 0
    392. numOut.N2 = 0
    393. numOut.N3 = 0
    394. numOut.N4 = 0
    395. numOut.N5 = 0
    396. numOut.N6 = 0
    397. numOut.N7 = 0
    398. numOut.N8 = 0
    399. numOut.N9 = 0
    400. End Sub
    401. ' Add/subtract two numbers. The inputs must be in reduced form, and the
    402. ' output isn't, so to do another addition or subtraction on the output,
    403. ' first multiply it by one to reduce it.
    404. Public Shared Sub Add(ByRef xy As Long10, ByRef x As Long10, ByRef y As Long10)
    405. xy.N0 = x.N0 + y.N0
    406. xy.N1 = x.N1 + y.N1
    407. xy.N2 = x.N2 + y.N2
    408. xy.N3 = x.N3 + y.N3
    409. xy.N4 = x.N4 + y.N4
    410. xy.N5 = x.N5 + y.N5
    411. xy.N6 = x.N6 + y.N6
    412. xy.N7 = x.N7 + y.N7
    413. xy.N8 = x.N8 + y.N8
    414. xy.N9 = x.N9 + y.N9
    415. End Sub
    416. Public Shared Sub [Sub](ByRef xy As Long10, ByRef x As Long10, ByRef y As Long10)
    417. xy.N0 = x.N0 - y.N0
    418. xy.N1 = x.N1 - y.N1
    419. xy.N2 = x.N2 - y.N2
    420. xy.N3 = x.N3 - y.N3
    421. xy.N4 = x.N4 - y.N4
    422. xy.N5 = x.N5 - y.N5
    423. xy.N6 = x.N6 - y.N6
    424. xy.N7 = x.N7 - y.N7
    425. xy.N8 = x.N8 - y.N8
    426. xy.N9 = x.N9 - y.N9
    427. End Sub
    428. ''' <summary>
    429. ''' Multiply a number by a small integer in range -185861411 .. 185861411.
    430. ''' The output is in reduced form, the input x need not be. x and xy may point
    431. ''' to the same buffer.
    432. ''' </summary>
    433. Public Shared Sub MulSmall(ByRef xy As Long10, ByRef x As Long10, ByRef y As Long)
    434. Dim temp As Long = x.N8 * y
    435. xy.N8 = temp And ((1 << 26) - 1)
    436. temp = (temp >> 26) + (x.N9 * y)
    437. xy.N9 = temp And ((1 << 25) - 1)
    438. temp = 19 * (temp >> 25) + (x.N0 * y)
    439. xy.N0 = temp And ((1 << 26) - 1)
    440. temp = (temp >> 26) + (x.N1 * y)
    441. xy.N1 = temp And ((1 << 25) - 1)
    442. temp = (temp >> 25) + (x.N2 * y)
    443. xy.N2 = temp And ((1 << 26) - 1)
    444. temp = (temp >> 26) + (x.N3 * y)
    445. xy.N3 = temp And ((1 << 25) - 1)
    446. temp = (temp >> 25) + (x.N4 * y)
    447. xy.N4 = temp And ((1 << 26) - 1)
    448. temp = (temp >> 26) + (x.N5 * y)
    449. xy.N5 = temp And ((1 << 25) - 1)
    450. temp = (temp >> 25) + (x.N6 * y)
    451. xy.N6 = temp And ((1 << 26) - 1)
    452. temp = (temp >> 26) + (x.N7 * y)
    453. xy.N7 = temp And ((1 << 25) - 1)
    454. temp = (temp >> 25) + xy.N8
    455. xy.N8 = temp And ((1 << 26) - 1)
    456. xy.N9 += temp >> 26
    457. End Sub
    458. ''' <summary>
    459. ''' Multiply two numbers. The output is in reduced form, the inputs need not be.
    460. ''' </summary>
    461. Public Shared Sub Multiply(ByRef xy As Long10, ByRef x As Long10, ByRef y As Long10)
    462. ' sahn0:
    463. ' Using local variables to avoid class access.
    464. ' This seem to improve performance a bit...
    465. '
    466. Dim x0 As Long = x.N0, x1 As Long = x.N1, x2 As Long = x.N2, x3 As Long = x.N3, x4 As Long = x.N4, x5 As Long = x.N5, x6 As Long = x.N6, x7 As Long = x.N7, x8 As Long = x.N8, x9 As Long = x.N9
    467. Dim y0 As Long = y.N0, y1 As Long = y.N1, y2 As Long = y.N2, y3 As Long = y.N3, y4 As Long = y.N4, y5 As Long = y.N5, y6 As Long = y.N6, y7 As Long = y.N7, y8 As Long = y.N8, y9 As Long = y.N9
    468. Dim t As Long = (x0 * y8) + (x2 * y6) + (x4 * y4) + (x6 * y2) + (x8 * y0) + 2 * ((x1 * y7) + (x3 * y5) + (x5 * y3) + (x7 * y1)) + 38 * (x9 * y9)
    469. xy.N8 = t And ((1 << 26) - 1)
    470. t = (t >> 26) + (x0 * y9) + (x1 * y8) + (x2 * y7) + (x3 * y6) + (x4 * y5) + (x5 * y4) + (x6 * y3) + (x7 * y2) + (x8 * y1) + (x9 * y0)
    471. xy.N9 = t And ((1 << 25) - 1)
    472. t = (x0 * y0) + 19 * ((t >> 25) + (x2 * y8) + (x4 * y6) + (x6 * y4) + (x8 * y2)) + 38 * ((x1 * y9) + (x3 * y7) + (x5 * y5) + (x7 * y3) + (x9 * y1))
    473. xy.N0 = t And ((1 << 26) - 1)
    474. t = (t >> 26) + (x0 * y1) + (x1 * y0) + 19 * ((x2 * y9) + (x3 * y8) + (x4 * y7) + (x5 * y6) + (x6 * y5) + (x7 * y4) + (x8 * y3) + (x9 * y2))
    475. xy.N1 = t And ((1 << 25) - 1)
    476. t = (t >> 25) + (x0 * y2) + (x2 * y0) + 19 * ((x4 * y8) + (x6 * y6) + (x8 * y4)) + 2 * (x1 * y1) + 38 * ((x3 * y9) + (x5 * y7) + (x7 * y5) + (x9 * y3))
    477. xy.N2 = t And ((1 << 26) - 1)
    478. t = (t >> 26) + (x0 * y3) + (x1 * y2) + (x2 * y1) + (x3 * y0) + 19 * ((x4 * y9) + (x5 * y8) + (x6 * y7) + (x7 * y6) + (x8 * y5) + (x9 * y4))
    479. xy.N3 = t And ((1 << 25) - 1)
    480. t = (t >> 25) + (x0 * y4) + (x2 * y2) + (x4 * y0) + 19 * ((x6 * y8) + (x8 * y6)) + 2 * ((x1 * y3) + (x3 * y1)) + 38 * ((x5 * y9) + (x7 * y7) + (x9 * y5))
    481. xy.N4 = t And ((1 << 26) - 1)
    482. t = (t >> 26) + (x0 * y5) + (x1 * y4) + (x2 * y3) + (x3 * y2) + (x4 * y1) + (x5 * y0) + 19 * ((x6 * y9) + (x7 * y8) + (x8 * y7) + (x9 * y6))
    483. xy.N5 = t And ((1 << 25) - 1)
    484. t = (t >> 25) + (x0 * y6) + (x2 * y4) + (x4 * y2) + (x6 * y0) + 19 * (x8 * y8) + 2 * ((x1 * y5) + (x3 * y3) + (x5 * y1)) + 38 * ((x7 * y9) + (x9 * y7))
    485. xy.N6 = t And ((1 << 26) - 1)
    486. t = (t >> 26) + (x0 * y7) + (x1 * y6) + (x2 * y5) + (x3 * y4) + (x4 * y3) + (x5 * y2) + (x6 * y1) + (x7 * y0) + 19 * ((x8 * y9) + (x9 * y8))
    487. xy.N7 = t And ((1 << 25) - 1)
    488. t = (t >> 25) + xy.N8
    489. xy.N8 = t And ((1 << 26) - 1)
    490. xy.N9 += (t >> 26)
    491. End Sub
    492. ''' <summary>
    493. ''' Square a number. Optimization of Multiply(x2, x, x)
    494. ''' </summary>
    495. Public Shared Sub Square(ByRef xsqr As Long10, ByRef x As Long10)
    496. Dim x0 As Long = x.N0, x1 As Long = x.N1, x2 As Long = x.N2, x3 As Long = x.N3, x4 As Long = x.N4, x5 As Long = x.N5, x6 As Long = x.N6, x7 As Long = x.N7, x8 As Long = x.N8, x9 As Long = x.N9
    497. Dim t As Long = (x4 * x4) + 2 * ((x0 * x8) + (x2 * x6)) + 38 * (x9 * x9) + 4 * ((x1 * x7) + (x3 * x5))
    498. xsqr.N8 = t And ((1 << 26) - 1)
    499. t = (t >> 26) + 2 * ((x0 * x9) + (x1 * x8) + (x2 * x7) + (x3 * x6) + (x4 * x5))
    500. xsqr.N9 = t And ((1 << 25) - 1)
    501. t = 19 * (t >> 25) + (x0 * x0) + 38 * ((x2 * x8) + (x4 * x6) + (x5 * x5)) + 76 * ((x1 * x9) + (x3 * x7))
    502. xsqr.N0 = t And ((1 << 26) - 1)
    503. t = (t >> 26) + 2 * (x0 * x1) + 38 * ((x2 * x9) + (x3 * x8) + (x4 * x7) + (x5 * x6))
    504. xsqr.N1 = t And ((1 << 25) - 1)
    505. t = (t >> 25) + 19 * (x6 * x6) + 2 * ((x0 * x2) + (x1 * x1)) + 38 * (x4 * x8) + 76 * ((x3 * x9) + (x5 * x7))
    506. xsqr.N2 = t And ((1 << 26) - 1)
    507. t = (t >> 26) + 2 * ((x0 * x3) + (x1 * x2)) + 38 * ((x4 * x9) + (x5 * x8) + (x6 * x7))
    508. xsqr.N3 = t And ((1 << 25) - 1)
    509. t = (t >> 25) + (x2 * x2) + 2 * (x0 * x4) + 38 * ((x6 * x8) + (x7 * x7)) + 4 * (x1 * x3) + 76 * (x5 * x9)
    510. xsqr.N4 = t And ((1 << 26) - 1)
    511. t = (t >> 26) + 2 * ((x0 * x5) + (x1 * x4) + (x2 * x3)) + 38 * ((x6 * x9) + (x7 * x8))
    512. xsqr.N5 = t And ((1 << 25) - 1)
    513. t = (t >> 25) + 19 * (x8 * x8) + 2 * ((x0 * x6) + (x2 * x4) + (x3 * x3)) + 4 * (x1 * x5) + 76 * (x7 * x9)
    514. xsqr.N6 = t And ((1 << 26) - 1)
    515. t = (t >> 26) + 2 * ((x0 * x7) + (x1 * x6) + (x2 * x5) + (x3 * x4)) + 38 * (x8 * x9)
    516. xsqr.N7 = t And ((1 << 25) - 1)
    517. t = (t >> 25) + xsqr.N8
    518. xsqr.N8 = t And ((1 << 26) - 1)
    519. xsqr.N9 += (t >> 26)
    520. End Sub
    521. ''' <summary>
    522. ''' Calculates a reciprocal. The output is in reduced form, the inputs need not
    523. ''' be. Simply calculates y = x^(p-2) so it's not too fast. */
    524. ''' When sqrtassist is true, it instead calculates y = x^((p-5)/8)
    525. ''' </summary>
    526. Public Shared Sub Reciprocal(ByRef y As Long10, ByRef x As Long10, ByRef sqrtAssist As Boolean)
    527. 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()
    528. Dim i As Integer
    529. ' the chain for x^(2^255-21) is straight from djb's implementation
    530. Square(t1, x) ' 2 == 2 * 1
    531. Square(t2, t1) ' 4 == 2 * 2
    532. Square(t0, t2) ' 8 == 2 * 4
    533. Multiply(t2, t0, x) ' 9 == 8 + 1
    534. Multiply(t0, t2, t1) ' 11 == 9 + 2
    535. Square(t1, t0) ' 22 == 2 * 11
    536. Multiply(t3, t1, t2) ' 31 == 22 + 9
    537. ' == 2^5 - 2^0
    538. Square(t1, t3) ' 2^6 - 2^1
    539. Square(t2, t1) ' 2^7 - 2^2
    540. Square(t1, t2) ' 2^8 - 2^3
    541. Square(t2, t1) ' 2^9 - 2^4
    542. Square(t1, t2) ' 2^10 - 2^5
    543. Multiply(t2, t1, t3) ' 2^10 - 2^0
    544. Square(t1, t2) ' 2^11 - 2^1
    545. Square(t3, t1) ' 2^12 - 2^2
    546. For i = 1 To 5 - 1
    547. Square(t1, t3)
    548. Square(t3, t1)
    549. Next ' t3
    550. ' 2^20 - 2^10
    551. Multiply(t1, t3, t2) ' 2^20 - 2^0
    552. Square(t3, t1) ' 2^21 - 2^1
    553. Square(t4, t3) ' 2^22 - 2^2
    554. For i = 1 To 10 - 1
    555. Square(t3, t4)
    556. Square(t4, t3)
    557. Next ' t4
    558. ' 2^40 - 2^20
    559. Multiply(t3, t4, t1) ' 2^40 - 2^0
    560. For i = 0 To 5 - 1
    561. Square(t1, t3)
    562. Square(t3, t1)
    563. Next ' t3
    564. ' 2^50 - 2^10
    565. Multiply(t1, t3, t2) ' 2^50 - 2^0
    566. Square(t2, t1) ' 2^51 - 2^1
    567. Square(t3, t2) ' 2^52 - 2^2
    568. For i = 1 To 25 - 1
    569. Square(t2, t3)
    570. Square(t3, t2)
    571. Next ' t3
    572. ' 2^100 - 2^50
    573. Multiply(t2, t3, t1) ' 2^100 - 2^0
    574. Square(t3, t2) ' 2^101 - 2^1
    575. Square(t4, t3) ' 2^102 - 2^2
    576. For i = 1 To 50 - 1
    577. Square(t3, t4)
    578. Square(t4, t3)
    579. Next ' t4
    580. ' 2^200 - 2^100
    581. Multiply(t3, t4, t2) ' 2^200 - 2^0
    582. For i = 0 To 25 - 1
    583. Square(t4, t3)
    584. Square(t3, t4)
    585. Next ' t3
    586. ' 2^250 - 2^50
    587. Multiply(t2, t3, t1) ' 2^250 - 2^0
    588. Square(t1, t2) ' 2^251 - 2^1
    589. Square(t2, t1) ' 2^252 - 2^2
    590. If sqrtAssist Then
    591. Multiply(y, x, t2) ' 2^252 - 3
    592. Else
    593. Square(t1, t2) ' 2^253 - 2^3
    594. Square(t2, t1) ' 2^254 - 2^4
    595. Square(t1, t2) ' 2^255 - 2^5
    596. Multiply(y, t1, t0) ' 2^255 - 21
    597. End If
    598. End Sub
    599. ''' <summary>
    600. ''' Checks if x is "negative", requires reduced input
    601. ''' </summary>
    602. ''' <param name="x">must be reduced input</param>
    603. Public Shared Function IsNegative(ByVal x As Long10) As Integer
    604. Return CInt(If(IsOverflow(x) Or x.N9 < 0, 1, 0) Xor x.N0 And 1)
    605. End Function
    606. ' ******************* Elliptic curve ********************
    607. ' y^2 = x^3 + 486662 x^2 + x over GF(2^255-19)
    608. ' t1 = ax + az
    609. ' t2 = ax - az
    610. Private Shared Sub MontyPrepare(ByVal t1 As Long10, ByVal t2 As Long10, ByVal ax As Long10, ByVal az As Long10)
    611. Add(t1, ax, az)
    612. [Sub](t2, ax, az)
    613. End Sub
    614. ' A = P + Q where
    615. ' X(A) = ax/az
    616. ' X(P) = (t1+t2)/(t1-t2)
    617. ' X(Q) = (t3+t4)/(t3-t4)
    618. ' X(P-Q) = dx
    619. ' clobbers t1 and t2, preserves t3 and t4
    620. Private Shared Sub MontyAdd(ByVal t1 As Long10, ByVal t2 As Long10, ByVal t3 As Long10, ByVal t4 As Long10, ByVal ax As Long10, ByVal az As Long10, ByVal dx As Long10)
    621. Multiply(ax, t2, t3)
    622. Multiply(az, t1, t4)
    623. Add(t1, ax, az)
    624. [Sub](t2, ax, az)
    625. Square(ax, t1)
    626. Square(t1, t2)
    627. Multiply(az, t1, dx)
    628. End Sub
    629. ' B = 2 * Q where
    630. ' X(B) = bx/bz
    631. ' X(Q) = (t3+t4)/(t3-t4)
    632. ' clobbers t1 and t2, preserves t3 and t4
    633. Private Shared Sub MontyDouble(ByVal t1 As Long10, ByVal t2 As Long10, ByVal t3 As Long10, ByVal t4 As Long10, ByVal bx As Long10, ByVal bz As Long10)
    634. Square(t1, t3)
    635. Square(t2, t4)
    636. Multiply(bx, t1, t2)
    637. [Sub](t2, t1, t2)
    638. MulSmall(bz, t2, 121665)
    639. Add(t1, t1, bz)
    640. Multiply(bz, t1, t2)
    641. End Sub
    642. ''' <summary>
    643. ''' Y^2 = X^3 + 486662 X^2 + X
    644. ''' </summary>
    645. ''' <param name="y2">output</param>
    646. ''' <param name="x">X</param>
    647. ''' <param name="temp">temporary</param>
    648. Public Shared Sub CurveEquationInline(ByRef y2 As Long10, ByRef x As Long10, ByRef temp As Long10)
    649. Square(temp, x)
    650. MulSmall(y2, x, 486662)
    651. Add(temp, temp, y2)
    652. temp.N0 += 1
    653. Multiply(y2, temp, x)
    654. End Sub
    655. ''' <summary>
    656. ''' P = kG and s = sign(P)/k
    657. ''' </summary>
    658. Public Shared Sub Core(ByRef publicKey As Byte(), ByRef signingKey As Byte(), ByRef privateKey As Byte(), ByRef peerPublicKey As Byte())
    659. If publicKey Is Nothing Then Throw New ArgumentNullException("publicKey")
    660. If publicKey.Length <> 32 Then Throw New ArgumentException(String.Format("publicKey must be 32 bytes long (but was {0} bytes long)", publicKey.Length), "publicKey")
    661. If signingKey IsNot Nothing AndAlso signingKey.Length <> 32 Then Throw New ArgumentException(String.Format("signingKey must be null or 32 bytes long (but was {0} bytes long)", signingKey.Length), "signingKey")
    662. If privateKey Is Nothing Then Throw New ArgumentNullException("privateKey")
    663. If privateKey.Length <> 32 Then Throw New ArgumentException(String.Format("privateKey must be 32 bytes long (but was {0} bytes long)", privateKey.Length), "privateKey")
    664. If peerPublicKey IsNot Nothing AndAlso peerPublicKey.Length <> 32 Then Throw New ArgumentException(String.Format("peerPublicKey must be null or 32 bytes long (but was {0} bytes long)", peerPublicKey.Length), "peerPublicKey")
    665. 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()
    666. Dim x As Long10() = {New Long10(), New Long10()}, z As Long10() = {New Long10(), New Long10()}
    667. ' unpack the base
    668. If peerPublicKey IsNot Nothing Then
    669. Unpack(dx, peerPublicKey)
    670. Else
    671. [Set](dx, 9)
    672. End If
    673. ' 0G = point-at-infinity
    674. [Set](x(0), 1)
    675. [Set](z(0), 0)
    676. ' 1G = G
    677. Copy(x(1), dx)
    678. [Set](z(1), 1)
    679. Dim i As Integer = 32
    680. While Math.Max(Threading.Interlocked.Decrement(i), i + 1) <> 0
    681. Dim j As Integer = 8
    682. While Math.Max(Threading.Interlocked.Decrement(j), j + 1) <> 0
    683. ' swap arguments depending on bit
    684. Dim bit1 As Integer = (privateKey(i) And &HFF) >> j And 1
    685. Dim bit0 As Integer = Not (privateKey(i) And &HFF) >> j And 1
    686. Dim ax As Long10 = x(bit0)
    687. Dim az As Long10 = z(bit0)
    688. Dim bx As Long10 = x(bit1)
    689. Dim bz As Long10 = z(bit1)
    690. ' a' = a + b
    691. ' b' = 2 b
    692. MontyPrepare(t1, t2, ax, az)
    693. MontyPrepare(t3, t4, bx, bz)
    694. MontyAdd(t1, t2, t3, t4, ax, az, dx)
    695. MontyDouble(t1, t2, t3, t4, bx, bz)
    696. End While
    697. End While
    698. Reciprocal(t1, z(0), False)
    699. Multiply(dx, x(0), t1)
    700. Pack(dx, publicKey)
    701. ' calculate s such that s abs(P) = G .. assumes G is std base point
    702. If signingKey IsNot Nothing Then
    703. CurveEquationInline(t1, dx, t2) ' t1 = Py^2
    704. Reciprocal(t3, z(1), False) ' where Q=P+G ...
    705. Multiply(t2, x(1), t3) ' t2 = Qx
    706. Add(t2, t2, dx) ' t2 = Qx + Px
    707. t2.N0 += 9 + 486662 ' t2 = Qx + Px + Gx + 486662
    708. dx.N0 -= 9 ' dx = Px - Gx
    709. Square(t3, dx) ' t3 = (Px - Gx)^2
    710. Multiply(dx, t2, t3) ' dx = t2 (Px - Gx)^2
    711. [Sub](dx, dx, t1) ' dx = t2 (Px - Gx)^2 - Py^2
    712. dx.N0 -= 39420360 ' dx = t2 (Px - Gx)^2 - Py^2 - Gy^2
    713. Multiply(t1, dx, BaseR2Y) ' t1 = -Py
    714. If IsNegative(t1) <> 0 Then ' sign is 1, so just copy
    715. Copy32(privateKey, signingKey) ' sign is -1, so negate
    716. Else
    717. ' p[m..n+m-1] = q[m..n+m-1] + z * x
    718. ' n is the size of x
    719. ' n+m is the size of p and q
    720. 'Public Shared Function MultiplyArraySmall(p,q,m As Integer, x , n As Integer, z As Integer) As Integer
    721. MultiplyArraySmall(signingKey, OrderTimes8, 0, privateKey, 32, -1)
    722. End If
    723. ' reduce s mod q
    724. ' (is this needed? do it just in case, it's fast anyway)
    725. 'divmod((dstptr) t1, s, 32, order25519, 32);
    726. ' take reciprocal of s mod q
    727. Dim temp1 = New Byte(31) {}
    728. Dim temp2 = New Byte(63) {}
    729. Dim temp3 = New Byte(63) {}
    730. Copy32(Order, temp1)
    731. Dim Egcd32Result() As Byte = Egcd32(temp2, temp3, signingKey, temp1)
    732. Copy32(Egcd32Result, signingKey)
    733. If (signingKey(31) And &H80) <> 0 Then MultiplyArraySmall(signingKey, signingKey, 0, Order, 32, 1)
    734. End If
    735. End Sub
    736. ''' <summary>
    737. ''' Smallest multiple of the order that's >= 2^255
    738. ''' </summary>
    739. Private Shared ReadOnly OrderTimes8 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}
    740. ''' <summary>
    741. ''' Constant 1/(2Gy)
    742. ''' </summary>
    743. Public Shared ReadOnly BaseR2Y As Long10 = New Long10(5744, 8160848, 4790893, 13779497, 35730846, 12541209, 49101323, 30047407, 40071253, 6226132)
    744. End Class
    745. End Namespace





    Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „evolver“ ()

    Hallo,
    ich habs nun nach ein paar kleine Stellschrauben geschafft, nun wird auch der SignKey richtig generiert. Hier nun die funzende Curve25519 in VB.NET (sieht zwar nicht schön aus, ist aber funktionell):
    Spoiler anzeigen

    Quellcode

    1. ' Ported parts from Java to C# and refactored by Hans Wolff, 17/09/2013
    2. ' Ported from C to Java by Dmitry Skiba [sahn0], 23/02/08.
    3. ' Original: http://code.google.com/p/curve25519-java/
    4. '
    5. ' Generic 64-bit integer implementation of Curve25519 ECDH
    6. ' Written by Matthijs van Duin, 200608242056
    7. ' Public domain.
    8. '
    9. ' Based on work by Daniel J Bernstein, http://cr.yp.to/ecdh.html
    10. '
    11. Option Strict On
    12. Imports Microsoft.VisualBasic
    13. Imports System
    14. Imports System.Security.Cryptography
    15. Namespace Elliptic
    16. Public Class RefCurve25519
    17. ' key size
    18. Public Const KeySize As Integer = 32
    19. ' group order (a prime near 2^252+2^124)
    20. Public Shared ReadOnly 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}
    21. #Region "******* KEY AGREEMENT ********"
    22. ''' <summary>
    23. ''' Private key clamping (inline, for performance)
    24. ''' </summary>
    25. ''' <param name="key">[out] 32 random bytes</param>
    26. Public Shared Sub ClampPrivateKeyInline(ByVal key As Byte())
    27. If key Is Nothing Then Throw New ArgumentNullException("key")
    28. If key.Length <> 32 Then Throw New ArgumentException(String.Format("key must be 32 bytes long (but was {0} bytes long)", key.Length))
    29. key(31) = CByte(key(31) And &H7F)
    30. key(31) = CByte(key(31) Or &H40)
    31. key(0) = CByte(key(0) And &HF8)
    32. End Sub
    33. ''' <summary>
    34. ''' Private key clamping
    35. ''' </summary>
    36. ''' <param name="rawKey">[out] 32 random bytes</param>
    37. Public Shared Function ClampPrivateKey(ByVal rawKey As Byte()) As Byte()
    38. If rawKey Is Nothing Then Throw New ArgumentNullException("rawKey")
    39. If rawKey.Length <> 32 Then Throw New ArgumentException(String.Format("rawKey must be 32 bytes long (but was {0} bytes long)", rawKey.Length), "rawKey")
    40. Dim res = New Byte(31) {}
    41. Array.Copy(rawKey, res, 32)
    42. res(31) = CByte(res(31) And &H7F)
    43. res(31) = CByte(res(31) Or &H40)
    44. res(0) = CByte(res(0) And &HF8)
    45. Return res
    46. End Function
    47. ''' <summary>
    48. ''' Creates a random private key
    49. ''' </summary>
    50. ''' <returns>32 random bytes that are clamped to a suitable private key</returns>
    51. Public Shared Function CreateRandomPrivateKey() As Byte()
    52. Dim privateKey = New Byte(31) {}
    53. RandomNumberGenerator.Create().GetBytes(privateKey)
    54. ClampPrivateKeyInline(privateKey)
    55. Return privateKey
    56. End Function
    57. ''' <summary>
    58. ''' Key-pair generation (inline, for performance)
    59. ''' </summary>
    60. ''' <param name="publicKey">[out] public key</param>
    61. ''' <param name="signingKey">[out] signing key (ignored if NULL)</param>
    62. ''' <param name="privateKey">[out] private key</param>
    63. ''' <remarks>WARNING: if signingKey is not NULL, this function has data-dependent timing</remarks>
    64. Public Shared Sub KeyGenInline(ByVal publicKey As Byte(), ByVal signingKey As Byte(), ByVal privateKey As Byte())
    65. If publicKey Is Nothing Then Throw New ArgumentNullException("publicKey")
    66. If publicKey.Length <> 32 Then Throw New ArgumentException(String.Format("publicKey must be 32 bytes long (but was {0} bytes long)", publicKey.Length), "publicKey")
    67. If signingKey Is Nothing Then Throw New ArgumentNullException("signingKey")
    68. If signingKey.Length <> 32 Then Throw New ArgumentException(String.Format("signingKey must be 32 bytes long (but was {0} bytes long)", signingKey.Length), "signingKey")
    69. If privateKey Is Nothing Then Throw New ArgumentNullException("privateKey")
    70. If privateKey.Length <> 32 Then Throw New ArgumentException(String.Format("privateKey must be 32 bytes long (but was {0} bytes long)", privateKey.Length), "privateKey")
    71. RandomNumberGenerator.Create().GetBytes(privateKey)
    72. ClampPrivateKeyInline(privateKey)
    73. Core(publicKey, signingKey, privateKey, Nothing)
    74. End Sub
    75. ''' <summary>
    76. ''' Generates the public key out of the clamped private key
    77. ''' </summary>
    78. ''' <param name="privateKey">private key (must use ClampPrivateKey first!)</param>
    79. Public Shared Function GetPublicKey(ByVal privateKey As Byte()) As Byte()
    80. Dim publicKey = New Byte(31) {}
    81. Core(publicKey, Nothing, privateKey, Nothing)
    82. Return publicKey
    83. End Function
    84. ''' <summary>
    85. ''' Generates signing key out of the clamped private key
    86. ''' </summary>
    87. ''' <param name="privateKey">private key (must use ClampPrivateKey first!)</param>
    88. Public Shared Function GetSigningKey(ByRef publicKey As Byte(), ByRef signingKey As Byte(), ByVal privateKey As Byte()) As Byte()
    89. 'Dim signingKey = New Byte(31) {}
    90. 'Dim publicKey = New Byte(31) {}
    91. Core(publicKey, signingKey, privateKey, Nothing)
    92. Return signingKey
    93. End Function
    94. ''' <summary>
    95. ''' Key agreement
    96. ''' </summary>
    97. ''' <param name="privateKey">[in] your private key for key agreement</param>
    98. ''' <param name="peerPublicKey">[in] peer's public key</param>
    99. ''' <returns>shared secret (needs hashing before use)</returns>
    100. Public Shared Function GetSharedSecret(ByVal privateKey As Byte(), ByVal peerPublicKey As Byte()) As Byte()
    101. Dim sharedSecret = New Byte(31) {}
    102. Core(sharedSecret, Nothing, privateKey, peerPublicKey)
    103. Return sharedSecret
    104. End Function
    105. ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
    106. #End Region
    107. ' sahn0:
    108. ' Using this class instead of long[10] to avoid bounds checks.
    109. Public NotInheritable Class Long10
    110. Public Sub New()
    111. End Sub
    112. Public Sub New(ByVal n0 As Long, ByVal n1 As Long, ByVal n2 As Long, ByVal n3 As Long, ByVal n4 As Long, ByVal n5 As Long, ByVal n6 As Long, ByVal n7 As Long, ByVal n8 As Long, ByVal n9 As Long)
    113. Me.N0 = n0
    114. Me.N1 = n1
    115. Me.N2 = n2
    116. Me.N3 = n3
    117. Me.N4 = n4
    118. Me.N5 = n5
    119. Me.N6 = n6
    120. Me.N7 = n7
    121. Me.N8 = n8
    122. Me.N9 = n9
    123. End Sub
    124. Public N0, N1, N2, N3, N4, N5, N6, N7, N8, N9 As Long
    125. End Class
    126. ' ******************* radix 2^8 math ********************
    127. Public Shared Sub Copy32(source As Byte(), ByRef destination As Byte())
    128. Array.Copy(source, 0, destination, 0, 32)
    129. End Sub
    130. ' p[m..n+m-1] = q[m..n+m-1] + z * x
    131. ' n is the size of x
    132. ' n+m is the size of p and q
    133. Public Shared Function MultiplyArraySmall(ByRef p As Byte(), ByRef q As Byte(), m As Integer, x As Byte(), n As Integer, z As Integer) As Integer
    134. Dim v As Integer = 0
    135. For i As Integer = 0 To n - 1
    136. Dim temp = q(i + m)
    137. Dim temp1 = x(i)
    138. v += (temp And &HFF) + z * (temp1 And &HFF)
    139. Dim temp3 = BitConverter.GetBytes(v) ' CByte(v)
    140. Dim v1 As Byte = temp3(0)
    141. p(i + m) = v1
    142. v >>= 8
    143. Next
    144. Return v
    145. End Function
    146. ' p += x * y * z where z is a small integer
    147. ' x is size 32, y is size t, p is size 32+t
    148. ' y is allowed to overlap with p+32 if you don't care about the upper half
    149. Public Shared Sub MultiplyArray32(ByRef p As Byte(), x As Byte(), y As Byte(), t As Integer, z As Integer)
    150. Const n As Integer = 31
    151. Dim w As Integer = 0
    152. Dim i As Integer = 0
    153. While i < t
    154. Dim zy As Integer = z * (y(i) And &HFF)
    155. w += MultiplyArraySmall(p, p, i, x, n, zy) + (p(i + n) And &HFF) + zy * (x(n) And &HFF)
    156. p(i + n) = BitConverter.GetBytes(w)(0)
    157. w >>= 8
    158. i += 1
    159. End While
    160. p(i + n) = BitConverter.GetBytes(w + (p(i + n) And &HFF))(0)
    161. End Sub
    162. ' divide r (size n) by d (size t), returning quotient q and remainder r
    163. ' quotient is size n-t+1, remainder is size t
    164. ' requires t > 0 && d[t-1] != 0
    165. ' requires that r[-1] and d[-1] are valid memory locations
    166. ' q may overlap with r+t
    167. Public Shared Sub DivMod(ByRef q As Byte(), ByRef r As Byte(), n As Integer, d As Byte(), t As Integer)
    168. Dim rn As Integer = 0
    169. Dim dt As Integer = (d(t - 1) And &HFF) << 8
    170. If t > 1 Then
    171. dt = dt Or d(t - 2) And &HFF
    172. End If
    173. While Math.Max(Threading.Interlocked.Decrement(n), n + 1) >= t
    174. Dim z As Integer = (rn << 16) Or ((r(n) And &HFF) << 8)
    175. If n > 0 Then
    176. z = z Or r(n - 1) And &HFF
    177. End If
    178. z = CInt(z / dt)
    179. rn += MultiplyArraySmall(r, r, n - t + 1, d, t, -z)
    180. Dim temp = CByte(z + rn And &HFF) ' rn is 0 or -1 (underflow)
    181. Dim temp1 = n - t + 1
    182. q(temp1) = temp
    183. MultiplyArraySmall(r, r, n - t + 1, d, t, -rn)
    184. rn = r(n) And &HFF
    185. r(n) = 0
    186. End While
    187. r(t - 1) = CByte(rn)
    188. End Sub
    189. Private Shared Function GetNumSize(ByVal num As Byte(), ByVal maxSize As Integer) As Integer
    190. For i = maxSize - 1 To 0 Step -1
    191. If num(i) <> 0 Then Return i + 1
    192. Next
    193. Return 0
    194. End Function
    195. ''' <summary>
    196. ''' Returns x if a contains the gcd, y if b.
    197. ''' </summary>
    198. ''' <param name="x">x and y must have 64 bytes space for temporary use.</param>
    199. ''' <param name="y">x and y must have 64 bytes space for temporary use.</param>
    200. ''' <param name="a">requires that a[-1] and b[-1] are valid memory locations</param>
    201. ''' <param name="b">requires that a[-1] and b[-1] are valid memory locations</param>
    202. ''' <returns>Also, the returned buffer contains the inverse of a mod b as 32-byte signed.</returns>
    203. Private Shared Function Egcd32(ByRef x As Byte(), ByRef y As Byte(), a As Byte(), ByRef b As Byte()) As Byte()
    204. Dim bn As Integer = 32
    205. Dim i As Integer
    206. For i = 0 To 32 - 1
    207. x(i) = y(i)
    208. y(i) = 0
    209. Next
    210. x(0) = 1
    211. Dim an As Integer = GetNumSize(a, 32)
    212. If an = 0 Then Return y ' division by zero
    213. Dim temp = New Byte(31) {}
    214. While True
    215. Dim qn As Integer = bn - an + 1
    216. DivMod(temp, b, bn, a, an)
    217. bn = GetNumSize(b, bn)
    218. If bn = 0 Then
    219. Return x
    220. End If
    221. MultiplyArray32(y, x, temp, qn, -1)
    222. qn = an - bn + 1
    223. DivMod(temp, a, an, b, bn)
    224. an = GetNumSize(a, an)
    225. If an = 0 Then
    226. Return y
    227. End If
    228. MultiplyArray32(x, y, temp, qn, -1)
    229. End While
    230. 'TODO: Egcd32 Else Return
    231. End Function
    232. ' ******************* radix 2^25.5 GF(2^255-19) math ********************
    233. Private Const P25 As Integer = 33554431 ' (1 << 25) - 1
    234. Private Const P26 As Integer = 67108863 ' (1 << 26) - 1
    235. ' Convert to internal format from little-endian byte format
    236. Public Shared Sub Unpack(ByRef x As Long10, m As Byte())
    237. x.N0 = m(0) And &HFF Or (m(1) And &HFF) << 8 Or (m(2) And &HFF) << 16 Or (m(3) And &HFF And 3) << 24
    238. x.N1 = (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
    239. x.N2 = (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
    240. x.N3 = (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
    241. x.N4 = (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
    242. x.N5 = m(16) And &HFF Or (m(17) And &HFF) << 8 Or (m(18) And &HFF) << 16 Or (m(19) And &HFF And 1) << 24
    243. x.N6 = (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
    244. x.N7 = (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
    245. x.N8 = (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
    246. x.N9 = (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
    247. End Sub
    248. ''' <summary>
    249. ''' Check if reduced-form input >= 2^255-19
    250. ''' </summary>
    251. Private Shared Function IsOverflow(ByVal x As Long10) As Boolean
    252. Return x.N0 > P26 - 19 And (x.N1 And x.N3 And x.N5 And x.N7 And x.N9) = P25 And (x.N2 And x.N4 And x.N6 And x.N8) = P26 OrElse x.N9 > P25
    253. End Function
    254. ' Convert from internal format to little-endian byte format. The
    255. ' number must be in a reduced form which is output by the following ops:
    256. ' unpack, mul, sqr
    257. ' set -- if input in range 0 .. P25
    258. ' If you're unsure if the number is reduced, first multiply it by 1.
    259. Public Shared Sub Pack(x As Long10, ByRef m As Byte())
    260. Dim ld As Integer = If(IsOverflow(x), 1, 0) - If(x.N9 < 0, 1, 0)
    261. Dim ud As Integer = ld * -(P25 + 1)
    262. ld *= 19
    263. Dim t As Long = ld + x.N0 + (x.N1 << 26)
    264. Dim bAry() As Byte = BitConverter.GetBytes(t)
    265. m(0) = bAry(0) ' CByte(t)
    266. m(1) = bAry(1) ' CByte(t >> 8)
    267. m(2) = bAry(2) ' CByte(t >> 16)
    268. m(3) = bAry(3) ' CByte(t >> 24)
    269. t = (t >> 32) + (x.N2 << 19)
    270. bAry = BitConverter.GetBytes(t)
    271. m(4) = bAry(0) ' CByte(t)
    272. m(5) = bAry(1) ' CByte(t >> 8)
    273. m(6) = bAry(2) ' CByte(t >> 16)
    274. m(7) = bAry(3) ' CByte(t >> 24)
    275. t = (t >> 32) + (x.N3 << 13)
    276. bAry = BitConverter.GetBytes(t)
    277. m(8) = bAry(0) ' CByte(t)
    278. m(9) = bAry(1) ' CByte(t >> 8)
    279. m(10) = bAry(2) ' CByte(t >> 16)
    280. m(11) = bAry(3) ' CByte(t >> 24)
    281. t = (t >> 32) + (x.N4 << 6)
    282. bAry = BitConverter.GetBytes(t)
    283. m(12) = bAry(0) ' CByte(t)
    284. m(13) = bAry(1) ' CByte(t >> 8)
    285. m(14) = bAry(2) ' CByte(t >> 16)
    286. m(15) = bAry(3) ' CByte(t >> 24)
    287. t = (t >> 32) + x.N5 + (x.N6 << 25)
    288. bAry = BitConverter.GetBytes(t)
    289. m(16) = bAry(0) ' CByte(t)
    290. m(17) = bAry(1) ' CByte(t >> 8)
    291. m(18) = bAry(2) ' CByte(t >> 16)
    292. m(19) = bAry(3) ' CByte(t >> 24)
    293. t = (t >> 32) + (x.N7 << 19)
    294. bAry = BitConverter.GetBytes(t)
    295. m(20) = bAry(0) ' CByte(t)
    296. m(21) = bAry(1) ' CByte(t >> 8)
    297. m(22) = bAry(2) ' CByte(t >> 16)
    298. m(23) = bAry(3) ' CByte(t >> 24)
    299. t = (t >> 32) + (x.N8 << 12)
    300. bAry = BitConverter.GetBytes(t)
    301. m(24) = bAry(0) ' CByte(t)
    302. m(25) = bAry(1) ' CByte(t >> 8)
    303. m(26) = bAry(2) ' CByte(t >> 16)
    304. m(27) = bAry(3) ' CByte(t >> 24)
    305. t = (t >> 32) + (x.N9 + ud << 6)
    306. bAry = BitConverter.GetBytes(t)
    307. m(28) = bAry(0) ' CByte(t)
    308. m(29) = bAry(1) ' CByte(t >> 8)
    309. m(30) = bAry(2) ' CByte(t >> 16)
    310. m(31) = bAry(3) ' CByte(t >> 24)
    311. End Sub
    312. ''' <summary>
    313. ''' Copy a number
    314. ''' </summary>
    315. Public Shared Sub Copy(ByRef numOut As Long10, numIn As Long10)
    316. numOut.N0 = numIn.N0
    317. numOut.N1 = numIn.N1
    318. numOut.N2 = numIn.N2
    319. numOut.N3 = numIn.N3
    320. numOut.N4 = numIn.N4
    321. numOut.N5 = numIn.N5
    322. numOut.N6 = numIn.N6
    323. numOut.N7 = numIn.N7
    324. numOut.N8 = numIn.N8
    325. numOut.N9 = numIn.N9
    326. End Sub
    327. ''' <summary>
    328. ''' Set a number to value, which must be in range -185861411 .. 185861411
    329. ''' </summary>
    330. Public Shared Sub [Set](ByRef numOut As Long10, numIn As Integer)
    331. numOut.N0 = numIn
    332. numOut.N1 = 0
    333. numOut.N2 = 0
    334. numOut.N3 = 0
    335. numOut.N4 = 0
    336. numOut.N5 = 0
    337. numOut.N6 = 0
    338. numOut.N7 = 0
    339. numOut.N8 = 0
    340. numOut.N9 = 0
    341. End Sub
    342. ' Add/subtract two numbers. The inputs must be in reduced form, and the
    343. ' output isn't, so to do another addition or subtraction on the output,
    344. ' first multiply it by one to reduce it.
    345. Public Shared Sub Add(ByRef xy As Long10, x As Long10, y As Long10)
    346. xy.N0 = x.N0 + y.N0
    347. xy.N1 = x.N1 + y.N1
    348. xy.N2 = x.N2 + y.N2
    349. xy.N3 = x.N3 + y.N3
    350. xy.N4 = x.N4 + y.N4
    351. xy.N5 = x.N5 + y.N5
    352. xy.N6 = x.N6 + y.N6
    353. xy.N7 = x.N7 + y.N7
    354. xy.N8 = x.N8 + y.N8
    355. xy.N9 = x.N9 + y.N9
    356. End Sub
    357. Public Shared Sub [Sub](ByRef xy As Long10, x As Long10, y As Long10)
    358. xy.N0 = x.N0 - y.N0
    359. xy.N1 = x.N1 - y.N1
    360. xy.N2 = x.N2 - y.N2
    361. xy.N3 = x.N3 - y.N3
    362. xy.N4 = x.N4 - y.N4
    363. xy.N5 = x.N5 - y.N5
    364. xy.N6 = x.N6 - y.N6
    365. xy.N7 = x.N7 - y.N7
    366. xy.N8 = x.N8 - y.N8
    367. xy.N9 = x.N9 - y.N9
    368. End Sub
    369. ''' <summary>
    370. ''' Multiply a number by a small integer in range -185861411 .. 185861411.
    371. ''' The output is in reduced form, the input x need not be. x and xy may point
    372. ''' to the same buffer.
    373. ''' </summary>
    374. Public Shared Sub MulSmall(ByRef xy As Long10, x As Long10, y As Long)
    375. Dim temp As Long = x.N8 * y
    376. xy.N8 = temp And ((1 << 26) - 1)
    377. temp = (temp >> 26) + (x.N9 * y)
    378. xy.N9 = temp And ((1 << 25) - 1)
    379. temp = 19 * (temp >> 25) + (x.N0 * y)
    380. xy.N0 = temp And ((1 << 26) - 1)
    381. temp = (temp >> 26) + (x.N1 * y)
    382. xy.N1 = temp And ((1 << 25) - 1)
    383. temp = (temp >> 25) + (x.N2 * y)
    384. xy.N2 = temp And ((1 << 26) - 1)
    385. temp = (temp >> 26) + (x.N3 * y)
    386. xy.N3 = temp And ((1 << 25) - 1)
    387. temp = (temp >> 25) + (x.N4 * y)
    388. xy.N4 = temp And ((1 << 26) - 1)
    389. temp = (temp >> 26) + (x.N5 * y)
    390. xy.N5 = temp And ((1 << 25) - 1)
    391. temp = (temp >> 25) + (x.N6 * y)
    392. xy.N6 = temp And ((1 << 26) - 1)
    393. temp = (temp >> 26) + (x.N7 * y)
    394. xy.N7 = temp And ((1 << 25) - 1)
    395. temp = (temp >> 25) + xy.N8
    396. xy.N8 = temp And ((1 << 26) - 1)
    397. xy.N9 += temp >> 26
    398. End Sub
    399. ''' <summary>
    400. ''' Multiply two numbers. The output is in reduced form, the inputs need not be.
    401. ''' </summary>
    402. Public Shared Sub Multiply(ByRef xy As Long10, x As Long10, y As Long10)
    403. ' sahn0:
    404. ' Using local variables to avoid class access.
    405. ' This seem to improve performance a bit...
    406. '
    407. Dim x0 As Long = x.N0, x1 As Long = x.N1, x2 As Long = x.N2, x3 As Long = x.N3, x4 As Long = x.N4, x5 As Long = x.N5, x6 As Long = x.N6, x7 As Long = x.N7, x8 As Long = x.N8, x9 As Long = x.N9
    408. Dim y0 As Long = y.N0, y1 As Long = y.N1, y2 As Long = y.N2, y3 As Long = y.N3, y4 As Long = y.N4, y5 As Long = y.N5, y6 As Long = y.N6, y7 As Long = y.N7, y8 As Long = y.N8, y9 As Long = y.N9
    409. Dim t As Long = (x0 * y8) + (x2 * y6) + (x4 * y4) + (x6 * y2) + (x8 * y0) + 2 * ((x1 * y7) + (x3 * y5) + (x5 * y3) + (x7 * y1)) + 38 * (x9 * y9)
    410. xy.N8 = t And ((1 << 26) - 1)
    411. t = (t >> 26) + (x0 * y9) + (x1 * y8) + (x2 * y7) + (x3 * y6) + (x4 * y5) + (x5 * y4) + (x6 * y3) + (x7 * y2) + (x8 * y1) + (x9 * y0)
    412. xy.N9 = t And ((1 << 25) - 1)
    413. t = (x0 * y0) + 19 * ((t >> 25) + (x2 * y8) + (x4 * y6) + (x6 * y4) + (x8 * y2)) + 38 * ((x1 * y9) + (x3 * y7) + (x5 * y5) + (x7 * y3) + (x9 * y1))
    414. xy.N0 = t And ((1 << 26) - 1)
    415. t = (t >> 26) + (x0 * y1) + (x1 * y0) + 19 * ((x2 * y9) + (x3 * y8) + (x4 * y7) + (x5 * y6) + (x6 * y5) + (x7 * y4) + (x8 * y3) + (x9 * y2))
    416. xy.N1 = t And ((1 << 25) - 1)
    417. t = (t >> 25) + (x0 * y2) + (x2 * y0) + 19 * ((x4 * y8) + (x6 * y6) + (x8 * y4)) + 2 * (x1 * y1) + 38 * ((x3 * y9) + (x5 * y7) + (x7 * y5) + (x9 * y3))
    418. xy.N2 = t And ((1 << 26) - 1)
    419. t = (t >> 26) + (x0 * y3) + (x1 * y2) + (x2 * y1) + (x3 * y0) + 19 * ((x4 * y9) + (x5 * y8) + (x6 * y7) + (x7 * y6) + (x8 * y5) + (x9 * y4))
    420. xy.N3 = t And ((1 << 25) - 1)
    421. t = (t >> 25) + (x0 * y4) + (x2 * y2) + (x4 * y0) + 19 * ((x6 * y8) + (x8 * y6)) + 2 * ((x1 * y3) + (x3 * y1)) + 38 * ((x5 * y9) + (x7 * y7) + (x9 * y5))
    422. xy.N4 = t And ((1 << 26) - 1)
    423. t = (t >> 26) + (x0 * y5) + (x1 * y4) + (x2 * y3) + (x3 * y2) + (x4 * y1) + (x5 * y0) + 19 * ((x6 * y9) + (x7 * y8) + (x8 * y7) + (x9 * y6))
    424. xy.N5 = t And ((1 << 25) - 1)
    425. t = (t >> 25) + (x0 * y6) + (x2 * y4) + (x4 * y2) + (x6 * y0) + 19 * (x8 * y8) + 2 * ((x1 * y5) + (x3 * y3) + (x5 * y1)) + 38 * ((x7 * y9) + (x9 * y7))
    426. xy.N6 = t And ((1 << 26) - 1)
    427. t = (t >> 26) + (x0 * y7) + (x1 * y6) + (x2 * y5) + (x3 * y4) + (x4 * y3) + (x5 * y2) + (x6 * y1) + (x7 * y0) + 19 * ((x8 * y9) + (x9 * y8))
    428. xy.N7 = t And ((1 << 25) - 1)
    429. t = (t >> 25) + xy.N8
    430. xy.N8 = t And ((1 << 26) - 1)
    431. xy.N9 += (t >> 26)
    432. End Sub
    433. ''' <summary>
    434. ''' Square a number. Optimization of Multiply(x2, x, x)
    435. ''' </summary>
    436. Public Shared Sub Square(ByRef xsqr As Long10, x As Long10)
    437. Dim x0 As Long = x.N0, x1 As Long = x.N1, x2 As Long = x.N2, x3 As Long = x.N3, x4 As Long = x.N4, x5 As Long = x.N5, x6 As Long = x.N6, x7 As Long = x.N7, x8 As Long = x.N8, x9 As Long = x.N9
    438. Dim t As Long = (x4 * x4) + 2 * ((x0 * x8) + (x2 * x6)) + 38 * (x9 * x9) + 4 * ((x1 * x7) + (x3 * x5))
    439. xsqr.N8 = t And ((1 << 26) - 1)
    440. t = (t >> 26) + 2 * ((x0 * x9) + (x1 * x8) + (x2 * x7) + (x3 * x6) + (x4 * x5))
    441. xsqr.N9 = t And ((1 << 25) - 1)
    442. t = 19 * (t >> 25) + (x0 * x0) + 38 * ((x2 * x8) + (x4 * x6) + (x5 * x5)) + 76 * ((x1 * x9) + (x3 * x7))
    443. xsqr.N0 = t And ((1 << 26) - 1)
    444. t = (t >> 26) + 2 * (x0 * x1) + 38 * ((x2 * x9) + (x3 * x8) + (x4 * x7) + (x5 * x6))
    445. xsqr.N1 = t And ((1 << 25) - 1)
    446. t = (t >> 25) + 19 * (x6 * x6) + 2 * ((x0 * x2) + (x1 * x1)) + 38 * (x4 * x8) + 76 * ((x3 * x9) + (x5 * x7))
    447. xsqr.N2 = t And ((1 << 26) - 1)
    448. t = (t >> 26) + 2 * ((x0 * x3) + (x1 * x2)) + 38 * ((x4 * x9) + (x5 * x8) + (x6 * x7))
    449. xsqr.N3 = t And ((1 << 25) - 1)
    450. t = (t >> 25) + (x2 * x2) + 2 * (x0 * x4) + 38 * ((x6 * x8) + (x7 * x7)) + 4 * (x1 * x3) + 76 * (x5 * x9)
    451. xsqr.N4 = t And ((1 << 26) - 1)
    452. t = (t >> 26) + 2 * ((x0 * x5) + (x1 * x4) + (x2 * x3)) + 38 * ((x6 * x9) + (x7 * x8))
    453. xsqr.N5 = t And ((1 << 25) - 1)
    454. t = (t >> 25) + 19 * (x8 * x8) + 2 * ((x0 * x6) + (x2 * x4) + (x3 * x3)) + 4 * (x1 * x5) + 76 * (x7 * x9)
    455. xsqr.N6 = t And ((1 << 26) - 1)
    456. t = (t >> 26) + 2 * ((x0 * x7) + (x1 * x6) + (x2 * x5) + (x3 * x4)) + 38 * (x8 * x9)
    457. xsqr.N7 = t And ((1 << 25) - 1)
    458. t = (t >> 25) + xsqr.N8
    459. xsqr.N8 = t And ((1 << 26) - 1)
    460. xsqr.N9 += (t >> 26)
    461. End Sub
    462. ''' <summary>
    463. ''' Calculates a reciprocal. The output is in reduced form, the inputs need not
    464. ''' be. Simply calculates y = x^(p-2) so it's not too fast. */
    465. ''' When sqrtassist is true, it instead calculates y = x^((p-5)/8)
    466. ''' </summary>
    467. Public Shared Sub Reciprocal(ByRef y As Long10, x As Long10, sqrtAssist As Boolean)
    468. 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()
    469. Dim i As Integer
    470. ' the chain for x^(2^255-21) is straight from djb's implementation
    471. Square(t1, x) ' 2 == 2 * 1
    472. Square(t2, t1) ' 4 == 2 * 2
    473. Square(t0, t2) ' 8 == 2 * 4
    474. Multiply(t2, t0, x) ' 9 == 8 + 1
    475. Multiply(t0, t2, t1) ' 11 == 9 + 2
    476. Square(t1, t0) ' 22 == 2 * 11
    477. Multiply(t3, t1, t2) ' 31 == 22 + 9
    478. ' == 2^5 - 2^0
    479. Square(t1, t3) ' 2^6 - 2^1
    480. Square(t2, t1) ' 2^7 - 2^2
    481. Square(t1, t2) ' 2^8 - 2^3
    482. Square(t2, t1) ' 2^9 - 2^4
    483. Square(t1, t2) ' 2^10 - 2^5
    484. Multiply(t2, t1, t3) ' 2^10 - 2^0
    485. Square(t1, t2) ' 2^11 - 2^1
    486. Square(t3, t1) ' 2^12 - 2^2
    487. For i = 1 To 5 - 1
    488. Square(t1, t3)
    489. Square(t3, t1)
    490. Next ' t3
    491. ' 2^20 - 2^10
    492. Multiply(t1, t3, t2) ' 2^20 - 2^0
    493. Square(t3, t1) ' 2^21 - 2^1
    494. Square(t4, t3) ' 2^22 - 2^2
    495. For i = 1 To 10 - 1
    496. Square(t3, t4)
    497. Square(t4, t3)
    498. Next ' t4
    499. ' 2^40 - 2^20
    500. Multiply(t3, t4, t1) ' 2^40 - 2^0
    501. For i = 0 To 5 - 1
    502. Square(t1, t3)
    503. Square(t3, t1)
    504. Next ' t3
    505. ' 2^50 - 2^10
    506. Multiply(t1, t3, t2) ' 2^50 - 2^0
    507. Square(t2, t1) ' 2^51 - 2^1
    508. Square(t3, t2) ' 2^52 - 2^2
    509. For i = 1 To 25 - 1
    510. Square(t2, t3)
    511. Square(t3, t2)
    512. Next ' t3
    513. ' 2^100 - 2^50
    514. Multiply(t2, t3, t1) ' 2^100 - 2^0
    515. Square(t3, t2) ' 2^101 - 2^1
    516. Square(t4, t3) ' 2^102 - 2^2
    517. For i = 1 To 50 - 1
    518. Square(t3, t4)
    519. Square(t4, t3)
    520. Next ' t4
    521. ' 2^200 - 2^100
    522. Multiply(t3, t4, t2) ' 2^200 - 2^0
    523. For i = 0 To 25 - 1
    524. Square(t4, t3)
    525. Square(t3, t4)
    526. Next ' t3
    527. ' 2^250 - 2^50
    528. Multiply(t2, t3, t1) ' 2^250 - 2^0
    529. Square(t1, t2) ' 2^251 - 2^1
    530. Square(t2, t1) ' 2^252 - 2^2
    531. If sqrtAssist Then
    532. Multiply(y, x, t2) ' 2^252 - 3
    533. Else
    534. Square(t1, t2) ' 2^253 - 2^3
    535. Square(t2, t1) ' 2^254 - 2^4
    536. Square(t1, t2) ' 2^255 - 2^5
    537. Multiply(y, t1, t0) ' 2^255 - 21
    538. End If
    539. End Sub
    540. ''' <summary>
    541. ''' Checks if x is "negative", requires reduced input
    542. ''' </summary>
    543. ''' <param name="x">must be reduced input</param>
    544. Public Shared Function IsNegative(ByVal x As Long10) As Integer
    545. Return CInt(If(IsOverflow(x) Or x.N9 < 0, 1, 0) Xor x.N0 And 1)
    546. End Function
    547. ' ******************* Elliptic curve ********************
    548. ' y^2 = x^3 + 486662 x^2 + x over GF(2^255-19)
    549. ' t1 = ax + az
    550. ' t2 = ax - az
    551. Public Shared Sub MontyPrepare(ByVal t1 As Long10, ByVal t2 As Long10, ByVal ax As Long10, ByVal az As Long10)
    552. Add(t1, ax, az)
    553. [Sub](t2, ax, az)
    554. End Sub
    555. ' A = P + Q where
    556. ' X(A) = ax/az
    557. ' X(P) = (t1+t2)/(t1-t2)
    558. ' X(Q) = (t3+t4)/(t3-t4)
    559. ' X(P-Q) = dx
    560. ' clobbers t1 and t2, preserves t3 and t4
    561. Public Shared Sub MontyAdd(ByVal t1 As Long10, ByVal t2 As Long10, ByVal t3 As Long10, ByVal t4 As Long10, ByVal ax As Long10, ByVal az As Long10, ByVal dx As Long10)
    562. Multiply(ax, t2, t3)
    563. Multiply(az, t1, t4)
    564. Add(t1, ax, az)
    565. [Sub](t2, ax, az)
    566. Square(ax, t1)
    567. Square(t1, t2)
    568. Multiply(az, t1, dx)
    569. End Sub
    570. ' B = 2 * Q where
    571. ' X(B) = bx/bz
    572. ' X(Q) = (t3+t4)/(t3-t4)
    573. ' clobbers t1 and t2, preserves t3 and t4
    574. Public Shared Sub MontyDouble(ByVal t1 As Long10, ByVal t2 As Long10, ByVal t3 As Long10, ByVal t4 As Long10, ByVal bx As Long10, ByVal bz As Long10)
    575. Square(t1, t3)
    576. Square(t2, t4)
    577. Multiply(bx, t1, t2)
    578. [Sub](t2, t1, t2)
    579. MulSmall(bz, t2, 121665)
    580. Add(t1, t1, bz)
    581. Multiply(bz, t1, t2)
    582. End Sub
    583. ''' <summary>
    584. ''' Y^2 = X^3 + 486662 X^2 + X
    585. ''' </summary>
    586. ''' <param name="y2">output</param>
    587. ''' <param name="x">X</param>
    588. ''' <param name="temp">temporary</param>
    589. Public Shared Sub CurveEquationInline(ByRef y2 As Long10, ByRef x As Long10, ByRef temp As Long10)
    590. Square(temp, x)
    591. MulSmall(y2, x, 486662)
    592. Add(temp, temp, y2)
    593. temp.N0 += 1
    594. Multiply(y2, temp, x)
    595. End Sub
    596. ''' <summary>
    597. ''' P = kG and s = sign(P)/k
    598. ''' </summary>
    599. Public Shared Sub Core(ByRef publicKey As Byte(), ByRef signingKey As Byte(), privateKey As Byte(), ByRef peerPublicKey As Byte())
    600. If publicKey Is Nothing Then Throw New ArgumentNullException("publicKey")
    601. If publicKey.Length <> 32 Then Throw New ArgumentException(String.Format("publicKey must be 32 bytes long (but was {0} bytes long)", publicKey.Length), "publicKey")
    602. If signingKey IsNot Nothing AndAlso signingKey.Length <> 32 Then Throw New ArgumentException(String.Format("signingKey must be null or 32 bytes long (but was {0} bytes long)", signingKey.Length), "signingKey")
    603. If privateKey Is Nothing Then Throw New ArgumentNullException("privateKey")
    604. If privateKey.Length <> 32 Then Throw New ArgumentException(String.Format("privateKey must be 32 bytes long (but was {0} bytes long)", privateKey.Length), "privateKey")
    605. If peerPublicKey IsNot Nothing AndAlso peerPublicKey.Length <> 32 Then Throw New ArgumentException(String.Format("peerPublicKey must be null or 32 bytes long (but was {0} bytes long)", peerPublicKey.Length), "peerPublicKey")
    606. 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()
    607. Dim x As Long10() = {New Long10(), New Long10()}, z As Long10() = {New Long10(), New Long10()}
    608. ' unpack the base
    609. If peerPublicKey IsNot Nothing Then
    610. Unpack(dx, peerPublicKey)
    611. Else
    612. [Set](dx, 9)
    613. End If
    614. ' 0G = point-at-infinity
    615. [Set](x(0), 1)
    616. [Set](z(0), 0)
    617. ' 1G = G
    618. Copy(x(1), dx)
    619. [Set](z(1), 1)
    620. Dim i As Integer = 32
    621. While Math.Max(Threading.Interlocked.Decrement(i), i + 1) <> 0
    622. Dim j As Integer = 8
    623. While Math.Max(Threading.Interlocked.Decrement(j), j + 1) <> 0
    624. ' swap arguments depending on bit
    625. Dim bit1 As Integer = (privateKey(i) And &HFF) >> j And 1
    626. Dim bit0 As Integer = Not (privateKey(i) And &HFF) >> j And 1
    627. Dim ax As Long10 = x(bit0)
    628. Dim az As Long10 = z(bit0)
    629. Dim bx As Long10 = x(bit1)
    630. Dim bz As Long10 = z(bit1)
    631. ' a' = a + b
    632. ' b' = 2 b
    633. MontyPrepare(t1, t2, ax, az)
    634. MontyPrepare(t3, t4, bx, bz)
    635. MontyAdd(t1, t2, t3, t4, ax, az, dx)
    636. MontyDouble(t1, t2, t3, t4, bx, bz)
    637. End While
    638. End While
    639. Reciprocal(t1, z(0), False)
    640. Multiply(dx, x(0), t1)
    641. Pack(dx, publicKey)
    642. ' calculate s such that s abs(P) = G .. assumes G is std base point
    643. If signingKey IsNot Nothing Then
    644. CurveEquationInline(t1, dx, t2) ' t1 = Py^2
    645. Reciprocal(t3, z(1), False) ' where Q=P+G ...
    646. Multiply(t2, x(1), t3) ' t2 = Qx
    647. Add(t2, t2, dx) ' t2 = Qx + Px
    648. t2.N0 += 9 + 486662 ' t2 = Qx + Px + Gx + 486662
    649. dx.N0 -= 9 ' dx = Px - Gx
    650. Square(t3, dx) ' t3 = (Px - Gx)^2
    651. Multiply(dx, t2, t3) ' dx = t2 (Px - Gx)^2
    652. [Sub](dx, dx, t1) ' dx = t2 (Px - Gx)^2 - Py^2
    653. dx.N0 -= 39420360 ' dx = t2 (Px - Gx)^2 - Py^2 - Gy^2
    654. Multiply(t1, dx, BaseR2Y) ' t1 = -Py
    655. If IsNegative(t1) <> 0 Then ' sign is 1, so just copy
    656. Copy32(privateKey, signingKey) ' sign is -1, so negate
    657. Else
    658. ' p[m..n+m-1] = q[m..n+m-1] + z * x
    659. ' n is the size of x
    660. ' n+m is the size of p and q
    661. 'Public Shared Function MultiplyArraySmall(p,q,m As Integer, x , n As Integer, z As Integer) As Integer
    662. MultiplyArraySmall(signingKey, OrderTimes8, 0, privateKey, 32, -1)
    663. End If
    664. ' reduce s mod q
    665. ' (is this needed? do it just in case, it's fast anyway)
    666. 'divmod((dstptr) t1, s, 32, order25519, 32);
    667. ' take reciprocal of s mod q
    668. Dim temp1 = New Byte(31) {}
    669. Dim temp2 = New Byte(63) {}
    670. Dim temp3 = New Byte(63) {}
    671. Copy32(Order, temp1)
    672. Dim Egcd32Result() As Byte = Egcd32(temp2, temp3, signingKey, temp1)
    673. Copy32(Egcd32Result, signingKey)
    674. If (signingKey(31) And &H80) <> 0 Then
    675. MultiplyArraySmall(signingKey, signingKey, 0, Order, 32, 1)
    676. End If
    677. End If
    678. End Sub
    679. ''' <summary>
    680. ''' Smallest multiple of the order that's >= 2^255
    681. ''' </summary>
    682. Private Shared ReadOnly OrderTimes8 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}
    683. ''' <summary>
    684. ''' Constant 1/(2Gy)
    685. ''' </summary>
    686. Public Shared ReadOnly BaseR2Y As Long10 = New Long10(5744, 8160848, 4790893, 13779497, 35730846, 12541209, 49101323, 30047407, 40071253, 6226132)
    687. End Class
    688. End Namespace