1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
import os
from Crypto.Util.number import getPrime as get_prime
from Crypto.Util.number import isPrime as is_prime
import secrets
import hashlib
# Computes the inverse of a mod prime p
def inverse(a, p):
return pow(a, p-2, p)
def hash(m):
h = hashlib.sha256(m).digest()
return int.from_bytes(h, 'big')
def generate_parameters():
# FIPS 186-4 specifies that p and q can be of (2048, 256) bits
while True:
q = get_prime(256)
r = secrets.randbits(2048-256)
p = r*q + 1
if p.bit_length() != 2048: continue
if not is_prime(p): continue
break
h = 1
while True:
h += 1
g = pow(h, (p-1)//q, p)
if g == 1: continue
break
return p, q, g
def sign(params, x, m):
p, q, g = params
k = secrets.randbelow(q)
r = pow(g, k, p) % q
s = inverse(k, q) * (hash(m) + x*r) % q
return (r, s)
def verify(params, y, m, sig):
p, q, g = params
r, s = sig
assert 0 < r < p
assert 0 < s < p
w = inverse(s, q)
u1 = hash(m) * w % q
u2 = r * w % q
v = pow(g, u1, p) * pow(y, u2, p) % p % q
assert v == r
def main():
# The parameters were generated by generate_parameters(), which will take some time to generate.
# With that reason, we will use a fixed one instead of a random one.
p = 17484281359996796703320753329289113133879315487679543624741105110874484027222384531803606958810995970161525595158267517181794414300756262340838882222415769778596720783078367872913954804658072233160036557319401158197234539657653635114116129319712841746177858547689703847179830876938850791424742190500438426350633498257950965188623233005750174576134802300600490139756306854032656842920490457629968890761814183283863329460516285392831741363925618264196019954486854731951282830652117210758060426483125525221398218382779387124491329788662015827601101640859700613929375036792053877746675842421482667089024073397901135900307
q = 113298192013516195145250438847099037276290008150762924677454979772524099733149
g = 2240914810379680126339108531401169275595161144670883986559069211999660898639987625873945546061830376966978596453328760234030133281772778843957617704660733666090807506024220142764237508766050356212712228439682713526208998745633642827205871276203625236122884797705545378063530457025121059332887929777555045770309256917282489323413372739717067924463128766609878574952525765509768641958927377639405729673058327662319958260422021309804322093360414034030331866591802559201326691178841972572277227570498592419367302032451643108376739154217604459747574970395332109358575481017157712896404133971465638098583730000464599930248
print(f'{p = }')
print(f'{q = }')
print(f'{g = }')
x = secrets.randbelow(q)
y = pow(g, x, p)
print(f'{y = }')
m = b'gib flag'
r = int(input('r = '))
s = int(input('s = '))
verify((p, q, g), y, m, (r, s))
flag = os.getenv('FLAG', 'hkcert24{***REDACTED***}')
print(flag)
if __name__ == '__main__':
main()
|
