q = 97 #q in wikipedia / p in slides / n in task description
m = 75
assert(g > 50)
--------------------------------------------------------------------------- NameError Traceback (most recent call last) Cell In[1], line 3 1 q = 97 #q in wikipedia / p in slides / n in task description 2 m = 75 ----> 3 assert(g > 50) NameError: name 'g' is not defined
2**5
32
from random import randrange
p = 97
d = randrange(1, p)
d
60
from sympy import primefactors
pf_ind = [(p-1)//div for div in primefactors(p-1)]
def check(g):
for index in pf_ind:
if g**index % p == 1:
return False
return True
for i in range(50, 70):
if check(i):
print(i)
56 57 58 59 60 68
[i for i in range(50, 90) if check(i)]
[56, 57, 58, 59, 60, 68, 71, 74, 76, 80, 82, 83, 84, 87]
from random import choice
g = choice([i for i in range(50, 90) if check(i)])
g
71
e = (g**d) % p
e
47
print("Public key (p, g, e):", p, g, e)
print("Secret key (d):", d)
Public key (p, g, e): 97 71 47 Secret key (d): 60
k = randrange(2, p)
r, s = (g**k) % p, (e**k * m) % p
print(r, s)
37 33
(s*r**(-d)) %p
2.6693805753843532e-93
$ s \cdot r^{-d} \mod p = \frac {s}{r^d} \mod p = s \cdot (r^d)^{-1} \mod p$
from sympy import mod_inverse
s*mod_inverse(r**d, p) % p
75
p = 9081321110693270343633073697474256143651
p.bit_length()
133
String -> Int
'ahoj'
'ahoj'
[ord(x)-64 for x in 'AHOJ']
[1, 8, 15, 10]
[ord(x)-ord('a')+1 for x in 'ahoj']
[1, 8, 15, 10]
[f'{ord(x)-64:02}' for x in 'AHOJ']
['01', '08', '15', '10']
"".join([f'{ord(x)-64:02}' for x in 'AHOJ'])
'01081510'
int("".join([f'{ord(x)-64:02}' for x in 'AHOJ']))
1081510
Int -> String
val = 1081510
res = ""
while val > 0:
res = chr(val % 100+64)+res
val = val // 100
res
'AHOJ'
a = 1
b = 6
p = 11
$ y^2 = x^3+a.x+b \mod p$
for x in range(p):
for y in range(p):
if (y*y - x*x*x-a*x-b) % p == 0:
print(x, y)
2 4 2 7 3 5 3 6 5 2 5 9 7 2 7 9 8 3 8 8 10 2 10 9
for y in range(p):
print(y, y*y % p)
0 0 1 1 2 4 3 9 4 5 5 3 6 3 7 5 8 9 9 4 10 1
Dictionary of squares {4: [2, 9], ...}.
Task is to find $x$ with appropriate $y^2$.
https://www.cryptool.org/en/jct/downloads
https://andrea.corbellini.name/ecc/interactive/modk-add.html