Skip to content

Instantly share code, notes, and snippets.

@samueltangz
Created December 16, 2019 01:50
Show Gist options
  • Save samueltangz/3aa4e1fcaf81ccc33dfbe441986e6af6 to your computer and use it in GitHub Desktop.
Save samueltangz/3aa4e1fcaf81ccc33dfbe441986e6af6 to your computer and use it in GitHub Desktop.
#!/usr/env/bin python
# -*- coding: UTF-8 -*-
from gmpy2 import powmod
import random
import dlog
m = 4902227890643
chars = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789{}_'
def n2st(n, length = 7):
global chars
if length == 0: return ''
ch = chars[n % len(chars)]
return n2st(n // len(chars), length - 1) + ch
def st2n(st):
global chars
n = 0
for i in range(7):
n = n * len(chars) + chars.find(st[i])
return n
def test():
for _ in xrange(100000):
n = random.randint(0, 65**7 - 1)
assert st2n(n2st(n)) == n
def recover_parameter():
global m
# f(0), f(1), ..., f(99)
sts = 'TgIgMEI Nh2uPF8 h5EMH{G sFKptgR inEPQXc 4aRyfng Mzj4Zs{ oZxYD9W H3ODU5z Sr5Bvaz BinXVvU YZ7dhJN NE9JtDv 81hAVhr oeoz}}u hcD5W4O wptHzx4 qQeVA8u mrzN50a HphlIPZ DcseJuk PWX}5wR 2}61cko uAVFCv0 _FvsUrY MgeHoFi E2{KDv9 Mke4E64 P2liD5D {RwEt4S hSFDKgT K}_wSHo YD0YmPl QzbhO8F {J8AdgN 5Vx40z8 ykhsiZV FUz7G37 d4lTM8p Gy1bvgB rpPacZh QJLdPOF Ukl1q4w HRlBIlF mcgBvHT 1GPDwl_ lnhtEf3 K}uxHwa yThJNcQ zwRGYca iOYjOJ3 fU827}i XBfy339 tu3Bolm }PBMAif Hppoakg YNTOf{R YUy5XyD z6DVzER 22JiLdF S7fdcUA YL2eFKV or7R8x1 UN{X9iA ex61}po i3PuRWV mfB3L90 GbMwMP6 0WLgQiD MitDZuP PX0hslB _CZf2DA EkSJqWe LIOqdHY _X_2Nj0 RbfZovC b2wG1il 20lF4kW D2f}O_h qnQCpcO wFIrDrw d5NeEfA pP7YLEe iJ82GiF {HaLkxM sq{Jq0v Jhl_Z77 QJMR9Ep {N2ndZH 3WyfX{d KIOcoLR FmzXGHM PZ5NyEu 0RmZOFC NbJdU6Z LEb33he 9SyzcSu DQHT2h_ LgTUncE tQUS2C}'.split(' ')
ns = [ st2n(st) for st in sts ]
# c, a, k, d unknown
# c*d = 1 (mod m)
# f(0) = k + c
# f(1) = k + a * c
# f(2) = k + a^2 * c
# ...
# (ns[1] - ns[0]) % m == (a - 1) * c
# (ns[2] - ns[1]) % m == (a^2 - a) * c == a * (a - 1) * c
a = (ns[2] - ns[1]) * powmod(ns[1] - ns[0], -1, m) % m
c = (ns[1] - ns[0]) * powmod(a - 1, -1, m) % m
d = powmod(c, -1, m)
k = (ns[0] - c) % m
return c, a, k, d
def solve():
global m
c, a, k, d = recover_parameter()
# k + a^n * c == 'watevr{'
a_pow_n = (st2n('watevr{') - k) * d % m
factors_phi_m = [ [ 2, 1 ], [ 163, 1 ], [ 5573, 1 ], [ 2698279, 1 ] ]
n = dlog.pohlig_hellman(a, a_pow_n, m, factors_phi_m)
assert n2st((k + pow(a, n, m) * c) % m) == 'watevr{'
s = ''
while s.find('}') == -1:
s += n2st((k + pow(a, n, m) * c) % m)
n += 1
flag = s.split('}')[0] + '}'
print flag
assert flag == 'watevr{S10P_B4BBLING}'
if __name__ == '__main__':
# test()
solve()
'''
f(n)
= c + k if n == 0
= k + [f(n/2) - k]^2 * d if n % 2 == 0
= k + a * [f(n/2) - k]^2 * d if n % 2 == 1
f(0) = k + c
f(1) = k + a * [f(0) - k]^2 * d
= k + a * c^2 * d
= k + a * c
f(2) = k + [f(1) - k]^2 * d
= k + a^2 * c^2 * d
= k + a^2 * c
f(3) = k + a * [f(1) - k]^2 * d
= k + a * a^2 * c^2 * d
= k + a^3 * c
f(4) = k + [f(2) - k]^2 * d
= k + a^4 * c
...
With MI we can show f(n) = k + a^n * c (mod m)
'''
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment