Shared173B-Homework / Homework9-173B / Homework 9.sagewsOpen in CoCalc
# Do your scratchwork at the bottom and put your finished code here.
# To receive full credit, these answers at the top must be easy to read.
%md
Who else is in your group? Sonia Dinh, Xiao Hu <br>
Whose worksheet would you like me to grade? Tony Sanchez<br><br>

Answer the following questions after you complete this homework: <br>
What is the value of the prime p? 881453108304409081743396544465246116426549710489364956229803 <br>
What is the value of the prime q? 73454425692034090145283045372038009296269214922740781296907<br>
What is the equation defining the elliptic curve E? y^2 = x^3 + 75815x + 42417<br>
What is the point P of order q? (348784099294644801210457854335002256619616638401292070122130 , 382877858618691410961184229366165007608825158328302838567310)<br>

What group did you perform an Elliptic Curve Diffie-Hellman key exchange with? Daniel Ngu's Group <br>
What was the secret message they sent you? 'andthesnakesstarttosing' <br>

Who else is in your group? Sonia Dinh, Xiao Hu
Whose worksheet would you like me to grade? Tony Sanchez

Answer the following questions after you complete this homework:
What is the value of the prime p? 881453108304409081743396544465246116426549710489364956229803
What is the value of the prime q? 73454425692034090145283045372038009296269214922740781296907
What is the equation defining the elliptic curve E? y^2 = x^3 + 75815x + 42417
What is the point P of order q? (348784099294644801210457854335002256619616638401292070122130 , 382877858618691410961184229366165007608825158328302838567310)

What group did you perform an Elliptic Curve Diffie-Hellman key exchange with? Daniel Ngu's Group
What was the secret message they sent you? 'andthesnakesstarttosing'

p = 0
while p % 4 != 3: # Making sure our prime p is congruent to 3 mod 4, so we can easily take square roots mod p later.
    p = random_prime(10^60, lbound = 10^59)
a = 0
b = 0
while (4*a**3+27*b**2) % p == 0: # Generating an Elliptic Curve with discriminant non zero.
    a = randint(1,100000)
    b = randint(1,100000)
E = EllipticCurve(GF(p),[a,b])
n = E.cardinality()

g = 2^4*3^2*5*7*11*13
while not is_prime(int(n/gcd(n,g))): # Making sure that our cardinality divided by a few small primes is prime.
    a = randint(1,100000)
    b = randint(1,100000)
    while (4*a**3+27*b**2) % p == 0: # Generating an Elliptic Curve with discriminant non zero.. again.
        a = randint(1,100000)
        b = randint(1,100000)
    E = EllipticCurve(GF(p),[a,b])
    n = E.cardinality()
q = n / gcd ( n , g ) # Here is our big prime which should be a divisor of our prime p and the other divisors should be small primes.
x = randint(0,p)
while legendre_symbol((x**3+a*x+b) % p,p) != 1: # Finding possible x values for a point on the elliptic curve.
    x = randint(0,p)
y1 = (x**3+a*x+b)%p
y = pow(int(y1),int((p+1)/4),p) # Using our rabin method to take square root to get y mod p
P = E(x,y) # Creating a point on the curve with our x and y values
O = P.order()
while O != q: # Ensuring our point has order q
    if gcd(O,q) > 1: # If q divides our order, then multiply the point by O/q to get a point with order q
        Q = int(O/q)
        P = P * Q
    else: # If not, generate a different x value and try again.
        x = randint(0,p)
        while legendre_symbol((x**3+a*x+b) % p,p) != 1:
            x = randint(0,p)
        y1 = (x**3+a*x+b)%p
        y = pow(int(y1),int((p+1)/4),p)
        P = E(x,y)
    O = P.order()
Na = randint(10^29, 10^30)
print Na
x = 348784099294644801210457854335002256619616638401292070122130
y = 382877858618691410961184229366165007608825158328302838567310
a = 75815
b = 42417
p = 881453108304409081743396544465246116426549710489364956229803 
E = EllipticCurve(GF(p),[a,b])
P = E(x,y)
NaP = Na * P
print P
print NaP
458536780217510204206756497497 (348784099294644801210457854335002256619616638401292070122130 : 382877858618691410961184229366165007608825158328302838567310 : 1) (123211986251719094404305238787806368688245743308349230941175 : 250998413975501816629213516464854265632057523615754582904511 : 1)
x = 641810271979307026612623949657725292466804078642745652664569
y = 11610574556424886431622399336728197540560259503097864032765
a = 75815
b = 42417
p = 881453108304409081743396544465246116426549710489364956229803 
E = EllipticCurve(GF(p),[a,b])
Nbp = E(x,y)
Na = 458536780217510204206756497497
Nabp = Na * Nbp
print Nabp
(212714705682624407212806475228733252375767276049545297651671 : 646338753711170682544795263966721795378518963225781455787414 : 1)
attach('Homework9-StarterCode.sage')
enciphervigenere('helloaliceifyouarereadingthisyouhavesuccesfullydecryptedmymessagemydebitcardpinnumberisanevennumberwith4digitsandthefirstdigitiseven',Integer(212714705682624407212806475228733252375767276049545297651671).digits())
'ILRMTGSREJMKHSUGYGYKHIPQIYJLVFWWJFCIYUKEFUMUPPAJGKXDPAIETANGTZGHJSFMGGMYLERJWKUTBRIHTNUDQLDGPSBQHEZYJVODMKKZUITITOIGPTTVEPMJYOZNXJR'
deciphervigenere('BUJUMKZWCPIXBXAXAVVYPSN',Integer(212714705682624407212806475228733252375767276049545297651671).digits())
'andthesnakesstarttosing'