Mirror of forum.nim-lang.org

522 :: Elliptic curve proc assimilation

• Cyther606 (orginal) [2014-08-12T05:31:13+02:00] view original

  Hello,

  I'm trying to convert this script to Nimrod. It's hanging at modinv, and I don't know why.

  import math, strutils
  
  proc `^`[T: float|int](base: T; exp: int): T =
    var (base, exp) = (base, exp)
    result = 1
    
    if exp < 0:
      when T is int:
        if base * base != 1: return 0
        elif (exp and 1) == 0: return 1
        else: return base
      else:
        base = 1.0 / base
        exp = -exp
    
    while exp != 0:
      if (exp and 1) != 0:
        result *= base
      exp = exp shr 1
      base *= base
  
  const
    Pcurve = 2.0^256 - 2.0^32 - 2.0^9 - 2.0^8 - 2.0^7 - 2.0^6 - 2.0^4 - 1.0
    N = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
    Acurve = 0
    Bcurve = 7
    Gx = 55066263022277343669578718895168534326250603453777594175500187360389116729240.0
    Gy = 32670510020758816978083085130507043184471273380659243275938904335757337482424.0
    GPoint = (Gx, Gy)
    privKey = 0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E
  
  proc modinv(a: float, n = Pcurve): float =
    var
      lm = 1.0
      hm = 0.0
      lowm = a mod n
      highm = n
    while lowm > 1.0:
      var
        ratio = highm / lowm
        nm = hm - (lm * ratio)
        temp = highm - (lowm * ratio)
        lm = nm
        lowm = temp
        hm = lm
        highm = lowm
    result = lm mod n
  
  proc ecAdd(a: tuple, b: tuple): tuple =
    var
      lamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0])) mod Pcurve
      x = (lamAdd * lamAdd - a[0] - b[0]) mod Pcurve
      y = (lamAdd * (a[0] - x) - a[1]) mod Pcurve
    result = (x, y)
  
  proc ecDouble(a: tuple): tuple =
    var
      lam = ((3 * a[0] * a[0] + Acurve) * modinv(2 * a[1])) mod Pcurve
      x = ((lam * lam) - (2 * a[0])) mod Pcurve
      y = (lam * (a[0] - x) - a[1]) mod Pcurve
    result = (x, y)
  
  proc ecMultiply(genPoint: tuple, scalarHex): tuple =
    if scalarHex == 0 or toBin(scalarHex, 64) >= toBin(N, 64):
      raise newException(E_base, "Invalid Scalar/Private Key")
    var
      scalarBin = toBin(scalarHex, 64)
      q = genPoint
    for i in 1 .. scalarBin.len:
      q = ecDouble(q)
      if scalarBin[i] == '1':
        q = ecAdd(q, genPoint)
    result = (q)
  
  proc main() =
    var publicKey = ecMultiply(GPoint, privKey)
    
    echo "******* Public Key Generation *********"
    echo "the private key: ", $privKey
    echo ""
    echo "the uncompressed public key (not address): " & $publicKey
    echo ""
    echo "the uncompressed public key (HEX): 04" & $publicKey[0] & $publicKey[1]
    echo ""
    echo "the official Public Key - compressed: ",
      if publicKey[1] mod 2 == 1:
        "03" & $toHex(toBiggestInt(publicKey[0]), 64)
      else:
        "02" & $toHex(toBiggestInt(publicKey[0]), 64)
  
  main()
  Run

  What am I missing?

---

• Jehan (orginal) [2014-08-12T07:01:50+02:00] view original

  You re-declare variables inside the loop that shadow the outer variables. However, the loop exit tests uses the outer variable lowm.

  You need something along the following lines (untested):

  
  proc modinv(a: float, n = Pcurve): float =
    var
      lm = 1.0
      hm = 0.0
      lowm = a mod n
      highm = n
    while lowm > 1.0:
      let
        ratio = highm / lowm
        nm = hm - (lm * ratio)
        temp = highm - (lowm * ratio)
      lm = nm
      lowm = temp
      hm = lm
      highm = lowm
    result = lm mod n
  Run

---

• Cyther606 (orginal) [2014-08-12T22:42:40+02:00] view original

  Thanks for your help. It works.

  Now, what accounts for the difference between how python and nimrod store hex values?

  python:

  >>> privKey = 0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E
  >>> print privKey
  72759466100064397073952777052424474334519735946222029294952053344302920927294
  Run

  nimrod:

  >>> let privKey = 0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E
  >>> echo privKey
  6063524273736419390
  Run

  I've tried importing printf from C and using ctypes with privKey and hex values to no avail.

---

• gradha (orginal) [2014-08-13T01:00:10+02:00] view original

  It is unfortunate that the compiler doesn't warn about the overflow, but Nimrod doesn't come with a bigint type. I don't think C does either, so that wouldn't help. If you want to store such big values you will need to use a special library like bigints which you can install through babel.

---

• Cyther606 (orginal) [2014-08-13T15:54:42+02:00] view original

  ok, installed bigints. bigints appears to work for Gx and Gy, but not for hex

  import bigints
  let
    Gx = initBigInt("55066263022277343669578718895168534326250603453777594175500187360389116729240")
    Gy = initBigInt("32670510020758816978083085130507043184471273380659243275938904335757337482424")
    privKey = initBigInt("0xA0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E")
  echo "Gx: ", Gx
  echo "Gy: ", Gy
  echo "privKey: ", privKey
  Run

  results

  Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240
  Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424
  privKey: 340142666630799874325011227401619526506411153385155426573377048844
  Run

  python:

  Run

  results

  Gx: 55066263022277343669578718895168534326250603453777594175500187360389116729240
  Gy: 32670510020758816978083085130507043184471273380659243275938904335757337482424
  privKey: 72759466100064397073952777052424474334519735946222029294952053344302920927294
  Run

---

• gradha (orginal) [2014-08-13T16:38:55+02:00] view original

  Strings can be anything, so you need to specify the base of the number in the constructor:

  
    privKey = initBigInt("A0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E", 16)
  Run

  Note you also have to remove the leading 0x since it is not parsed. I guess this might be a nice feature to have, you could ask the author to implement this kind of parsing or contribute it yourself.

---

• def (orginal) [2014-08-13T16:39:17+02:00] view original

  initBigInt doesn't parse 0x, but assumes decimal input by default. You can set another base like this:

  
  let privKey = initBigInt("A0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E", 16)
  Run

  I should change initBigInt to throw an error on invalid inputs though.

---

• Cyther606 (orginal) [2014-08-13T23:26:55+02:00] view original

  Thanks for the helpful instructions. Seems to be mostly working now, but feeding BigInts to toBin doesn't seem possible. Is it necessary to do something like this?

  include "system/inclrtl"
  proc toBin*(x: BigInt, len: int): string {.noSideEffect,
    rtl, extern: "nsuToBin".} =
    var
      mask = 1.initBigInt
      shift = 0.initBigInt
    assert(len > 0)
    result = newString(len)
    for j in countdown(len-1, 0):
      result[j] = chr(((x and mask) shr shift).initBigInt + ord('0'))
      shift = shift + 1
      mask = mask shl 1
  Run

  Code so far:

  import bigints, math, strutils
  
  proc `^`(base: int; exp: int): BigInt =
    let base = base.initBigInt
    var exp = exp
    result = 1.initBigInt
    while exp > 0:
      result *= base
      dec(exp)
  
  let
    Pcurve: BigInt = 2^256 - 2^32 - 2^9 - 2^8 - 2^7 - 2^6 - 2^4 - 1
    N = initBigInt("FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", 16)
    Acurve = 0
    Bcurve = 7
    Gx = initBigInt("55066263022277343669578718895168534326250603453777594175500187360389116729240")
    Gy = initBigInt("32670510020758816978083085130507043184471273380659243275938904335757337482424")
    Gpoint = (Gx, Gy)
    privKey = initBigInt("A0DC65FFCA799873CBEA0AC274015B9526505DAAAED385155425F7337704883E", 16)
  
  proc modinv(a: BigInt): BigInt =
    var
      lm = 1.initBigInt
      hm = 0.initBigInt
      lowm = a mod Pcurve
      highm = Pcurve
    while lowm > 1:
      let
        ratio = highm div lowm
        nm = hm - (lm * ratio)
        temp = highm - (lowm * ratio)
      lm = nm
      lowm = temp
      hm = lm
      highm = lowm
    result = lm mod Pcurve
  
  proc ecAdd(a: tuple, b: tuple): tuple =
    var
      lamAdd = ((b[1] - a[1]) * modinv(b[0] - a[0])) mod Pcurve
      x = (lamAdd * lamAdd - a[0] - b[0]) mod Pcurve
      y = (lamAdd * (a[0] - x) - a[1]) mod Pcurve
    result = (x, y)
  
  proc ecDouble(a: tuple): tuple =
    var
      lam = ((3 * a[0] * a[0] + Acurve) * modinv(2 * a[1])) mod Pcurve
      x = ((lam * lam) - (2 * a[0])) mod Pcurve
      y = (lam * (a[0] - x) - a[1]) mod Pcurve
    result = (x, y)
  
  proc ecMultiply(genPoint: tuple, scalarHex): tuple =
    if scalarHex == 0 or scalarHex >= N:
      raise newException(E_base, "Invalid Scalar/Private Key")
    var
      scalarBin = toBin(scalarHex, 64)
      q = genPoint
    for i in 1 .. scalarBin.len:
      q = ecDouble(q)
      if scalarBin[i] == '1':
        q = ecAdd(q, genPoint)
    result = (q)
  
  proc main() =
    let publicKey = ecMultiply(Gpoint, privKey)
    
    echo "******* Public Key Generation *********"
    echo "the private key: " & $privKey
    echo ""
    echo "the uncompressed public key (not address): " & $publicKey
    echo ""
    echo "the uncompressed public key (HEX): 04" & $publicKey[0] & $publicKey[1]
    echo ""
    echo "the official Public Key - compressed: ",
      if publicKey[1] mod 2 == 1:
        "03" & $toHex(toBiggestInt(publicKey[0]), 64)
      else:
        "02" & $toHex(toBiggestInt(publicKey[0]), 64)
  
  main()
  Run

---

• def (orginal) [2014-08-13T23:59:42+02:00] view original

  toBin is only for normal ints, not bigints. You can use

  
  scalarBin = scalarHex.toString(base = 2)
  Run

---

• Cyther606 (orginal) [2014-08-14T05:54:55+02:00] view original

  ok, thanks for that. The current BigInt code compiles successfully, but there is a discrepancy between the results of:

  # in ecDouble...
  lam = (3.initBigInt * a[0] * a[0] + Acurve) mod Pcurve
  Run

  and:

  # in ECdouble...
  Lam = (3*a[0]*a[0]+Acurve) % Pcurve
  Run

  It could be that 3.initBigInt is throwing things off, but I don't know why that would be.

---

• def (orginal) [2014-08-14T15:03:54+02:00] view original

  The immediate problem is your translation of modinv. This line:

  Run

  Should be

  
  hm = nm
  highm = temp
  swap hm, lm
  swap highm, lowm
  Run

  So the entire modinv is:

  
  proc modinv(a: BigInt): BigInt =
    var
      lm = 1.initBigInt
      hm = 0.initBigInt
      lowm = a mod Pcurve
      highm = Pcurve
    while lowm > 1:
      let
        ratio = highm div lowm
        nm = hm - (lm * ratio)
        temp = highm - (lowm * ratio)
      hm = nm
      highm = temp
      swap hm, lm
      swap highm, lowm
    result = lm mod Pcurve
  Run

  Unfortunately there is still a bug in the division of the bigints, so the result is still not right, even after fixing this. I'll try to fix the division later today. This one fails for example:

  
  echo initBigInt("756628490253123014067933708583503295844929075882239485540431356534910033618830501144105195285364489562157441837796863614070956636498456792910898817389940831543204657474297072356228690296487944931559885281889207062770782744748470400") mod initBigInt("115792089237316195423570985008687907853269984665640564039457584007908834671663")
  Run

  by returning

  
  91914488697929528343745639858918689573695451501517224372986149962429810193434
  Run

  instead of

  
  91914383230618135761690975197207778399550061809281766160147273830617914855857
  Run

---

• def (orginal) [2014-08-20T06:42:31+02:00] view original

  Sorry it took me so long, but it's working finally (albeit pretty slow, since the division of BigInts is not optimized).

  There was another bug in the printing of the keys, which have to be padded with leading 0s to length 64:

  
    echo "the uncompressed public key (HEX):"
    echo "04", publicKey[0].toString(base = 16).align(64, '0'), publicKey[1].toString(base = 16).align(64, '0')
    echo ""
    echo "the official Public Key - compressed:"
    echo if publicKey[1] mod 2 == 1: "03" & publicKey[0].toString(base = 16).align(64, '0')
         else: "02" & publicKey[0].toString(base = 16).align(64, '0')
  Run

  I fixed the division, and now the result looks exactly as in Python:

  ******* Public Key Generation *********
  
  the private key:
  72759466100064397073952777052424474334519735946222029294952053344302920927294
  
  the uncompressed public key (not address):
  (Field0: 3423904187495496827825042940737875085827330420143621346629173781207857376010, Field1: 75711134420273723792089656449854389054866833762486990555172221523628676983696)
  
  the uncompressed public key (HEX):
  040791dc70b75aa995213244ad3f4886d74d61ccd3ef658243fcad14c9ccee2b0aa762fbc6ac0921b8f17025bb8458b92794ae87a133894d70d7995fc0b6b5ab90
  
  the official Public Key - compressed:
  020791dc70b75aa995213244ad3f4886d74d61ccd3ef658243fcad14c9ccee2b0a

  The working version: https://github.com/def-/bigints/blob/master/examples/elliptic.nim

---

• Cyther606 (orginal) [2014-08-20T18:01:06+02:00] view original

  well done.

---