solve.py

from scryptos import *
import hashlib

'''
DEFCON Quals 2018 Official: Crypto part
Partial random-value Exposure Attack for DSA (<=> biased-k DSA)
References: https://crypto.stackexchange.com/questions/44644/how-does-the-biased-k-attack-on-ecdsa-work 
Thanks: @Bono_iPad and binja members
'''

y=128135682856750887590860168748824430714190353609169438003724812869569788088376999153566856518649548751808974042861313871720093923966663967385639616771013994922707548355367088446112595542221209828926608117506259743026809879227606814076195362151108590706375917914576011875357384956337974597411261584032533163073
p=145774370140705743619288815016506936272601276321515267981294709325646228235350799641396853482542510455702593145365689674776551326526283561120782331775753481248764911686023024656237178221049671999816376444280423000085773391715885524862881877222848088840644737895543531766907185051846802894682811137086905085419
q=739904609682520586736011252451716180456601329519
g=52865703933600072480340150084328845769706702669400766904467248075164948743170867377627486621900744105555465052783047541675343643777082719270261354312243195450389581166294097053506337884439282134405767273312076933070573084676163659758350542617531330447790290695414443063102502247168199735083467132847036144443

# collected data like `r,s`
# we collect 1500~ signatures but used only 100 signatures
rs_data = map(lambda z: map(int, z), filter(lambda y: y[0] != '', map(lambda x: x.split(','), open('rs_collect.txt').read().split('\n'))))

# verify
r, s = rs_data[0]
w = modinv(s, q)
H = int(hashlib.sha1('ls' + 'A' * (256 - 2)).hexdigest(), 16)
u1 = (H * w) % q
u2 = (r * w) % q
v = ((pow(g, u1, p) * pow(y, u2, p)) % p) % q
assert v == r

# we know the k's lowest byte is zero-filled <=> k = 2**8 * b
ell = 8

n = 100

# Matrix construction & Solve HNP using LLL
M = []
for i in xrange(n):
  M += [[0] * i + [q] + [0] * (n - i + 1)]
t_vec = []
u_vec = []
for i in xrange(n):
  r, s = rs_data[i]
  T = modinv(2**ell * s, q)
  t = (r * T) % q
  u = (-H * T) % q
  t_vec += [t]
  u_vec += [u]

# sentinel value
sT = 1
sU = 1

M += [t_vec + [sT, 0]]
M += [u_vec + [0, sU]]

print "[+] LLL"
B = LLL(M)

# Search Shortest & Useful Vector
for i, v in enumerate(B):
  if v[-1] == sT:
    x = -v[-2] / sU
    print x
    print x % q
    print (x % q).bit_length()
    break

solve_log

> python solve.py 
-61262266441191146369913672082151254217822682617
678642343241329440366097580369564926238778646902
159