Skip to content

Instantly share code, notes, and snippets.

@tscholl2

tscholl2/Curve25519.sage

Last active October 27, 2019 13:20
Show Gist options
  • Save tscholl2/412b6c8cc44c84debbe08c0cca98b42a to your computer and use it in GitHub Desktop.
Save tscholl2/412b6c8cc44c84debbe08c0cca98b42a to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tscholl2 renamed this gist Oct 27, 2019. 1 changed file with 0 additions and 0 deletions.
    0 NIST → NIST.sage
    View file
    File renamed without changes.
  2. tscholl2 revised this gist Oct 27, 2019. 1 changed file with 81 additions and 0 deletions.
    81 changes: 81 additions & 0 deletions NIST
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,81 @@
    # P-192
    p = 6277101735386680763835789423207666416083908700390324961279
    r = 6277101735386680763835789423176059013767194773182842284081
    s = 0x3045ae6fc8422f64ed579528d38120eae12196d5
    c = 0x3099d2bbbfcb2538542dcd5fb078b6ef5f3d6fe2c745de65
    b = 0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1
    Gx = 0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012
    Gy = 0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811

    # P-224
    p = 26959946667150639794667015087019630673557916260026308143510066298881
    r = 26959946667150639794667015087019625940457807714424391721682722368061
    s = 0xbd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5
    c = 0x5b056c7e11dd68f40469ee7f3c7a7d74f7d121116506d031218291fb
    b = 0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4
    Gx = 0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21
    Gy = 0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34

    # P-256
    p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
    r = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    s = 0xc49d360886e704936a6678e1139d26b7819f7e90
    c = 0x7efba1662985be9403cb055c75d4f7e0ce8d84a9c5114abcaf3177680104fa0d
    b = 0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b
    Gx = 0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296
    Gy = 0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5

    # P-384
    p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
    r = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
    s = 0xa335926aa319a27a1d00896a6773a4827acdac73
    c = 0x79d1e655f868f02fff48dcdee14151ddb80643c1406d0ca10dfe6fc52009540a495e8042ea5f744f6e184667cc722483
    b = 0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875ac656398d8a2ed19d2a85c8edd3ec2aef
    Gx = 0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a385502f25dbf55296c3a545e3872760ab7
    Gy = 0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c00a60b1ce1d7e819d7a431d7c90ea0e5f

    # P-512
    p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
    r = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449
    s = 0xd09e8800291cb85396cc6717393284aaa0da64ba
    c = 0x0b48bfa5f420a34949539d2bdfc264eeeeb077688e44fbf0ad8f6d0edb37bd6b533281000518e19f1b9ffbe0fe9ed8a3c2200b8f875e523868c70c1e5bf55bad637
    b = 0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef109e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00
    Gx = 0xc6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66
    Gy = 0x11839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650

    # Construction
    E = EllipticCurve(GF(p),[-3,b])
    G = E([Gx,Gy])
    assert r.is_prime(proof=False)
    # Verify order and base point
    assert r*G == 0
    assert (r-1)*G != 0
    assert abs(r - p) < 2*sqrt(p)
    # Verify pseudo-randomness
    import hashlib
    def int_to_bytes(x):
    s = ZZ(x).hex()
    if len(s)%2 == 1:
    s = "0" + s
    return "".join([chr(int(s[i:i+2],16)) for i in range(0,len(s),2)])
    def bytes_to_int(b):
    n = 0
    for c in [ord(x) for x in b]:
    n = (n<<8)|c
    return n
    def sha1int(x):
    h = hashlib.sha1()
    h.update(int_to_bytes(x))
    return h.digest()
    l = len(p.bits())
    v = floor((l-1)/160)
    w = l - 160*v - 1
    h = sha1int(s)
    h = h0 = int_to_bytes(bytes_to_int(h) % 2^w)
    z = s
    for i in [1..v]:
    si = (z+i) % 2^160
    hi = sha1int(si)
    h += hi
    assert c == bytes_to_int(h)
    assert GF(p)(b^2*c) == -27
  3. tscholl2 revised this gist Oct 27, 2019. 2 changed files with 7 additions and 1 deletion.
    7 changes: 7 additions & 0 deletions Curve25519.sage
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,7 @@
    # Curve25519
    p = 2^255 - 19
    N = 8*(2^252 + 27742317777372353535851937790883648493)
    E = EllipticCurve(GF(p),[0,486662,0,1,0])
    G = E.lift_x(9)
    assert E.count_points() == N
    assert G.order() == N/8
    1 change: 0 additions & 1 deletion SEC_Curves.sage → SEC.sage
    View file
    Original file line number Diff line number Diff line change
    @@ -73,4 +73,3 @@ b = 0x0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E1561939
    Gx= 0x00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66
    Gy= 0x011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650
    n = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409

  4. tscholl2 revised this gist Apr 4, 2019. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions SEC_Curves.sage
    View file
    Original file line number Diff line number Diff line change
    @@ -20,6 +20,7 @@ a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC
    b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
    Gx= 0x188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
    Gy= 0x07192B95FFC8DA78631011ED6B24CDD573F977A11E794811
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFF99DEF836146BC9B1B4D22831

    # 224k1
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFE56D
  5. tscholl2 revised this gist Apr 4, 2019. 1 changed file with 7 additions and 0 deletions.
    7 changes: 7 additions & 0 deletions SEC_Curves.sage
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,10 @@
    # To verify some properties:
    # E = EllipticCurve(GF(p),[a,b])
    # G = E([Gx,Gy])
    # assert n*G == 0
    # assert n.is_prime()
    # assert E.count_points() == n # all these curves have cofactor 1

    # 192k1
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37
    a = 0x000000000000000000000000000000000000000000000000
  6. tscholl2 created this gist Mar 24, 2019.
    68 changes: 68 additions & 0 deletions SEC_Curves.sage
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,68 @@
    # 192k1
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFEE37
    a = 0x000000000000000000000000000000000000000000000000
    b = 0x000000000000000000000000000000000000000000000003
    Gx= 0xDB4FF10EC057E9AE26B07D0280B7F4341DA5D1B1EAE06C7D
    Gy= 0x9B2F2F6D9C5628A7844163D015BE86344082AA88D95E2F9D
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFE26F2FC170F69466A74DEFD8D

    # 192r1
    S = 0x3045AE6FC8422F64ED579528D38120EAE12196D5
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFF
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFC
    b = 0x64210519E59C80E70FA7E9AB72243049FEB8DEECC146B9B1
    Gx= 0x188DA80EB03090F67CBF20EB43A18800F4FF0AFD82FF1012
    Gy= 0x07192B95FFC8DA78631011ED6B24CDD573F977A11E794811

    # 224k1
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFE56D
    a = 0x00000000000000000000000000000000000000000000000000000000
    b = 0x00000000000000000000000000000000000000000000000000000005
    Gx= 0xA1455B334DF099DF30FC28A169A467E9E47075A90F7E650EB6B7A45C
    Gy= 0x7E089FED7FBA344282CAFBD6F7E319F7C0B0BD59E2CA4BDB556D61A5
    n = 0x010000000000000000000000000001DCE8D2EC6184CAF0A971769FB1F7

    # 224r1
    S = 0xBD71344799D5C7FCDC45B59FA3B9AB8F6A948BC5
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF000000000000000000000001
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFFFFFFFFFFFFFFFFFE
    b = 0xB4050A850C04B3ABF54132565044B0B7D7BFD8BA270B39432355FFB4
    Gx= 0xB70E0CBD6BB4BF7F321390B94A03C1D356C21122343280D6115C1D21
    Gy= 0xBD376388B5F723FB4C22DFE6CD4375A05A07476444D5819985007E34
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFF16A2E0B8F03E13DD29455C5C2A3D

    # 256k1
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
    a = 0x0000000000000000000000000000000000000000000000000000000000000000
    b = 0x0000000000000000000000000000000000000000000000000000000000000007
    Gx= 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
    Gy= 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

    # 256r1
    S = 0xC49D360886E704936A6678E1139D26B7819F7E90
    p = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF
    a = 0xFFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC
    b = 0x5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B
    Gx= 0x6B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296
    Gy= 0x4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5
    n = 0xFFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551

    # 384r1
    S = 0xA335926AA319A27A1D00896A6773A4827ACDAC73
    p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFF
    a = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFFFF0000000000000000FFFFFFFC
    b = 0xB3312FA7E23EE7E4988E056BE3F82D19181D9C6EFE8141120314088F5013875AC656398D8A2ED19D2A85C8EDD3EC2AEF
    Gx= 0xAA87CA22BE8B05378EB1C71EF320AD746E1D3B628BA79B9859F741E082542A385502F25DBF55296C3A545E3872760AB7
    Gy= 0x3617DE4A96262C6F5D9E98BF9292DC29F8F41DBD289A147CE9DA3113B5F0B8C00A60B1CE1D7E819D7A431D7C90EA0E5F
    n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC7634D81F4372DDF581A0DB248B0A77AECEC196ACCC52973

    # 521r1
    S = 0xD09E8800291CB85396CC6717393284AAA0DA64BA
    p = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
    a = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC
    b = 0x0051953EB9618E1C9A1F929A21A0B68540EEA2DA725B99B315F3B8B489918EF109E156193951EC7E937B1652C0BD3BB1BF073573DF883D2C34F1EF451FD46B503F00
    Gx= 0x00C6858E06B70404E9CD9E3ECB662395B4429C648139053FB521F828AF606B4D3DBAA14B5E77EFE75928FE1DC127A2FFA8DE3348B3C1856A429BF97E7E31C2E5BD66
    Gy= 0x011839296A789A3BC0045C8A5FB42C7D1BD998F54449579B446817AFBD17273E662C97EE72995EF42640C550B9013FAD0761353C7086A272C24088BE94769FD16650
    n = 0x01FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFA51868783BF2F966B7FCC0148F709A5D03BB5C9B8899C47AEBB6FB71E91386409