]> git.somenet.org - pub/jan/ctf-seminar.git/blob - writeups/icecrax/asis2019/chinese_remainder_theorem.py
Update ctfzone19.md
[pub/jan/ctf-seminar.git] / writeups / icecrax / asis2019 / chinese_remainder_theorem.py
1 from functools import reduce
2 def chinese_remainder(n, a):
3     sum = 0
4     prod = reduce(lambda a, b: a*b, n)
5     for n_i, a_i in zip(n, a):
6         p = prod // n_i
7         sum += a_i * mul_inv(p, n_i) * p
8     return sum % prod
9  
10 def mul_inv(a, b):
11     b0 = b
12     x0, x1 = 0, 1
13     if b == 1: return 1
14     while a > 1:
15         q = a // b
16         a, b = b, a%b
17         x0, x1 = x1 - q * x0, x0
18     if x1 < 0: x1 += b0
19     return x1
20  
21
22 # Chinese Remainder Theorem:
23 # In number theory, the Chinese remainder theorem states that if one knows the remainders 
24 # of the Euclidean division of an integer n by several integers, then one can determine
25 # uniquely the remainder of the division of n by the product of these integers, under the
26 # condition that the divisors are pairwise coprime.
27
28 # What follows from the theorem:
29 # If M, N are coprime and A is coprime to M and N,
30 # then A is a quadratic residue modulo (M * N) if and only if it is a quadratic residue modulo M and modulo N
31 # a ≡ x^2 mod mn  =>  a ≡ x^2 mod m and a ≡ x^2 mod n.
32 # H ≡ pkey^2 mod p   => H ≡ pkey^2 mod p0 and H ≡ pkey^2 mod p1 ...
33
34 # Note:
35 # If each factor has 2 solutions, then for H we have 2*2*2*2 = 16 solutions
36 # To use the theorem all factors pi should be coprime gcd(pi, pj) = 1 !
37
38 if __name__ == '__main__':
39     p = 862718293348820473429344482784628181556388621521298319395315527974911
40     H = 381704527450191606347421195235742637659723827441243208291869156144963 # odd integer coprime to p
41  
42     factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593] # factors are coprime
43
44     r0 = [1104407, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
45     r1 = [1104407, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
46     r2 = [1104407, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
47     r3 = [1104407, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
48     r4 = [1104407, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
49     r5 = [1104407, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
50     r6 = [1104407, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
51     r7 = [1104407, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
52     r8 = [399666, 13380905, 25592602581952126, 159525640227776948659231897831230505709]
53     r9 = [399666, 13380905, 25592602581952126, 308269479959806774875048102517512730884]
54     r10 = [399666, 13380905, 34240854883018057, 159525640227776948659231897831230505709]
55     r11 = [399666, 13380905, 34240854883018057, 308269479959806774875048102517512730884]
56     r12 = [399666, 7111848, 25592602581952126, 159525640227776948659231897831230505709]
57     r13 = [399666, 7111848, 25592602581952126, 308269479959806774875048102517512730884]
58     r14 = [399666, 7111848, 34240854883018057, 159525640227776948659231897831230505709]
59     r15 = [399666, 7111848, 34240854883018057, 308269479959806774875048102517512730884]
60
61     rs = [r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15]
62     for r in rs:
63         print(chinese_remainder(factors, r))
64
65 # Results:
66 # 739258514585797449032297222084055811470702691611125687711372074996687
67 # 460372941321907147479217537764873459531020265638440613169538863817034
68 # 785232755191570522054580268914288666635203565395845945113513087262967
69 # 506347181927680220501500584595106314695521139423160870571679876083314
70 # 861011580078658110931573476857568388286745404020778288869777707662969
71 # 582126006814767809378493792538386036347062978048093214327944496483316
72 # 44267527335610710524512040903173061894857656284200226876603191954338
73 # 628100247420540882400776839368618891511563851832813471730085508749596
74 # 234618045928279591028567643416009290044824769688484847665230019225315
75 # 818450766013209762904832441881455119661530965237098092518712336020573
76 # 280592286534052664050850690246242145209325643473205105067371031491595
77 # 1706713270162362497771005927059793269643217500520030525537820311942
78 # 356371111421140252927843898189521866860867482098137448823635651891597
79 # 77485538157249951374764213870339514921185056125452374281802440711944
80 # 402345352026913325950126945019754722025368355882857706225776664157877
81 # 123459778763023024397047260700572370085685929910172631683943452978224