From 8e869e2f067d42c786db2c73c24e02ae06bca13d Mon Sep 17 00:00:00 2001 From: Steliyan Syarov Date: Tue, 3 Dec 2019 16:30:35 +0100 Subject: [PATCH] Add Bit Game exploit --- writeups/icecrax/asis2019.md | 48 ++-- .../asis2019/asis_single_bits_writeup.md | 239 ++++++++++++++++++ .../asis2019/chinese_remainder_theorem.py | 81 ++++++ writeups/icecrax/asis2019/exploit.py | 49 ++++ writeups/icecrax/asis2019/output.txt | 2 + writeups/icecrax/asis2019/single_bits.py | 48 ++++ writeups/icecrax/asis2019/tonelli-shanks.py | 66 +++++ .../understanding_duality_of_(c-t).py | 48 ++++ .../icecrax/asis2019/why_better_libraries.py | 26 ++ 9 files changed, 578 insertions(+), 29 deletions(-) create mode 100644 writeups/icecrax/asis2019/asis_single_bits_writeup.md create mode 100644 writeups/icecrax/asis2019/chinese_remainder_theorem.py create mode 100755 writeups/icecrax/asis2019/exploit.py create mode 100644 writeups/icecrax/asis2019/output.txt create mode 100755 writeups/icecrax/asis2019/single_bits.py create mode 100644 writeups/icecrax/asis2019/tonelli-shanks.py create mode 100644 writeups/icecrax/asis2019/understanding_duality_of_(c-t).py create mode 100644 writeups/icecrax/asis2019/why_better_libraries.py diff --git a/writeups/icecrax/asis2019.md b/writeups/icecrax/asis2019.md index 1e69fca..95eebfc 100644 --- a/writeups/icecrax/asis2019.md +++ b/writeups/icecrax/asis2019.md @@ -172,33 +172,23 @@ H = pkey[1] ** 2 % p print('H =', H) print('enc =', enc) ``` -I think I was on the right track on this one. Sadly this challenge was released on the last day and I didn't get the opportunity to spent more time on it. The CTF was over and the challenge was left unsolved... -Nevertheless that is what I managed to put together: -``` python -#enc = [...] -flag = '' -l = 5 -p = 862718293348820473429344482784628181556388621521298319395315527974911 -r = 738852413361336333302472130287418462898049591392380573449381971565615 -for i in range(len(enc)): - c = enc[i][0] - print("c: ",c) - t = enc[i][1] - print("t: ",t) - deca = ((-c-t) * r) % p - print("deca: ",deca) - b = bin(deca)[2:].count('1') - print("b: ", b) - if b == l: - flag += '0' - continue - deca = ((c-t) * r) % p - print("deca: ",deca) - a = bin(deca)[2:].count('1') - print("a: ",a) - if a == l: - flag += '1' - continue -print(hex(int(flag,2))[2:-1].decode('hex')) -``` \ No newline at end of file +I think I was on the right track on this one. Sadly this challenge was released on the last day and I didn't get the opportunity to solve it during the CTF. The CTF was over and the challenge was left unsolved. I had an Idea how to begin, but applying what I found didn't produce meaningful output. I continued working on it afterwards, since I spent the most time on it and I wanted to finish it. +Nevertheless this is what I managed to find out during the CTF: +Note: A lot of time the was spent reading articles, researching and understanding the underlying theorems and math applied. + + 1) Numbers produced by the 'gen_rand()' function are not completely random. Their binary representation always have five '1's. + + 2) Equation of the form x^2 ≡ q (mod n) are called "Quadratic residues". + + 3) Reversing H = pkey[1] ** 2 % p is a hard problem if 'p' was a prime, but since it is not, we could split it into factors and try to find solutions for all the individual factors pi: pkey^2 ≡ H (mod pi). + + 4) Legendre symbol or Euler’s Criterion can be used to check if a number is a quadratic residue. + + 5) The solutions from the individual factors can be combined via the "Chinese remainder theorem" to find a solution to the original problem, meaning we will find the public key. + + 6) For finding solutions to the individual problems there are two approaches: + - If `'a'` is a quadratic residue (mod p) and `p ≡ 3 (mod 4)` then `a^((p+1)/4)` is a solution to `x^2 ≡ a (mod p)`. + - If `a ≡ 1 (mod 4)` there is no analogous formula. In that case, one may use the "Tonelli-Shanks algorithm". + +PS: I posted a detailed solution for this challenge as well. \ No newline at end of file diff --git a/writeups/icecrax/asis2019/asis_single_bits_writeup.md b/writeups/icecrax/asis2019/asis_single_bits_writeup.md new file mode 100644 index 0000000..eda0848 --- /dev/null +++ b/writeups/icecrax/asis2019/asis_single_bits_writeup.md @@ -0,0 +1,239 @@ +# ASIS CTF Finals 2019 - Single bits (crypto / 194 points / 21 solves) +The ASIS CTF Finals consisted of 25 challenges, released on different time intervals (every 8 hours 8 or 9 challenges were being released). `Single bits` was released in the last 3rd phase of the CTF. I wasn't able to solve it during the competition, but I continued working on it after that. Solving it required a lot of research and good math knowledge to understand the theorems and apply them correctly. + +## Overview: +`Single bits` is a crypto reverse challenge. We were given two files: `single_bits.py` and `output.txt`. + +``` python +#!/usr/bin/env python + +import random +from Crypto.Util.number import * +from flag import flag + +def gen_rand(nbit, l): + R = [] + while True: + r = random.randint(0, nbit-1) + if r not in R: + R.append(r) + if len(R) == l: + break + R.sort() + rbit = '1' + for i in range(l-1): + rbit += (R[i+1] - R[i] - 1) * '0' + '1' + rbit += (nbit - R[-1] - 1) * '0' + return int(rbit, 2) + +def genkey(p, l): + n = len(bin(p)[2:]) + f, skey = gen_rand(n, l), gen_rand(n, l) + pkey = f * inverse(skey, p) % p + return (p, pkey), skey + +def encrypt(msg, pkey): + p, g = pkey + msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:]) + for b in bin(msg)[2:]: + s, t = gen_rand(n, l), gen_rand(n, l) + c = (s * g + t) % p + if b == '0': + enc.append((c, t)) + else: + enc.append((p-c, t)) + return enc + +p = 862718293348820473429344482784628181556388621521298319395315527974911 +l = 5 + +pkey, skey = genkey(p, l) +enc = encrypt(flag, pkey) +H = pkey[1] ** 2 % p + +print('H =', H) +print('enc =', enc) +``` + +The `output.txt` had the printed `'H'` and `'enc'` variables, where `H = 381704527450191606347421195235742637659723827441243208291869156144963` and `enc` was an array, consisting of every bit from the flag encrypted with the public key: `enc = [(693452030319839722726551032492658894345570855091353510812978453643631 374147273652096600518280302026002167242456968463360, ... `. + +## Short explanation of the given code: +1) Function `gen_rand(nbit, l)` takes 2 parameters, which are always equal to (229, 5). Then it produces 5 random numbers with a bit length of 229, sorts them and saves them into an array. For each number a `rbit` is calculated and all `rbits` are appended together. The final binary number is converted to int and returned. +__*It's worth noticing that although the `rbit` is calculated randomly, because we don't know the 2 numbers used to produce it, we always end up with a number, which binary representation has exactly five `'1'`s and many `'0'`. This information turned out to be useful later.*__ + +2) Function `genkey()` generates a public and a private key using `gen_rand()`. + +3) Function `encrypt()` again `gen_rand()` and the already created public key to encrypt every bit of the flag. For `'0'`s `'c'` is appended to the `'enc'` variable, for '`1'`s `'(p-c)'` + +## Solution / Exploit: +Since the public key is encrypted in H via `H = pkey[1] ** 2 % p`, the reverse engineering started from there. Googling this concrete equation lead me to a Wikipedia article about `Quadratic residues`, which explained in more detail the equation `x^2 ≡ q (mod n).` In our case this corresponds to `pkey^2 ≡ H (mod p)`. + +In general finding x is considered a hard problem, but in our case the modulo `'p'` is not a prime number and the solution requires much less time. We can factorize `'p'` and try to find solutions for all the factors pi: `pkey^2 ≡ H (mod pi)` and in the end combine those solutions using the `Chinese remainder theorem`. + + p = 862718293348820473429344482784628181556388621521298319395315527974911 + factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593] + +The Wikipedia article didn't have more information about how to solve the quadratic residue problem, only theorems determining if a number is one using the `Legendre symbol` or `Euler’s Criterion`. + +I found in another article on the internet two approaches to find a solution. + 1) If `'a'` is a quadratic residue (mod p) and `p ≡ 3 (mod 4)` then `a^((p+1)/4)` is a solution to `x^2 ≡ a (mod p)`. + 2) If `a ≡ 1 (mod 4)` there is no analogous formula. In that case, one may use the `Tonelli-Shanks algorithm`. + +It turned out that all the above factors (mod 4) give 1. So I found a python script with the `Tonnelli-Shanks algorithm` and it produced the following results: + + x^2 ≡ H (mod pi), where pi are prime numbers, factors of p + p0 = 1504073: + 399666 + 1104407 + + p1 = 20492753: + 7111848 + 13380905 + + p2 = 59833457464970183: + 34240854883018057 + 25592602581952126 + + p3 = 467795120187583723534280000348743236593: + 308269479959806774875048102517512730884 + 159525640227776948659231897831230505709 + +Each of the factors had 2 solutions. So from them using the `Chinese remainder theorem` I had to produce a solution for the original equation. And here I was stuck for a long time. I fed a python script implementing this algorithm the 8 solutions and their corresponding factors and because the factors were 4 and the solutions 8, I had to insert the factors twice. But that was the problem, because the numbers I had to input for the factors array had to be relatively prime to each other, meaning repeating them is not allowed! + +So I took the 8 solutions and I mixed them into 16 arrays and I fed each separately to the algorithm. It produced 16 possible public keys. + + r0 = [1104407, 13380905, 25592602581952126, 159525640227776948659231897831230505709] + r1 = [1104407, 13380905, 25592602581952126, 308269479959806774875048102517512730884] + r2 = [1104407, 13380905, 34240854883018057, 159525640227776948659231897831230505709] + r3 = [1104407, 13380905, 34240854883018057, 308269479959806774875048102517512730884] + r4 = [1104407, 7111848, 25592602581952126, 159525640227776948659231897831230505709] + r5 = [1104407, 7111848, 25592602581952126, 308269479959806774875048102517512730884] + r6 = [1104407, 7111848, 34240854883018057, 159525640227776948659231897831230505709] + r7 = [1104407, 7111848, 34240854883018057, 308269479959806774875048102517512730884] + r8 = [399666, 13380905, 25592602581952126, 159525640227776948659231897831230505709] + r9 = [399666, 13380905, 25592602581952126, 308269479959806774875048102517512730884] + r10 = [399666, 13380905, 34240854883018057, 159525640227776948659231897831230505709] + r11 = [399666, 13380905, 34240854883018057, 308269479959806774875048102517512730884] + r12 = [399666, 7111848, 25592602581952126, 159525640227776948659231897831230505709] + r13 = [399666, 7111848, 25592602581952126, 308269479959806774875048102517512730884] + r14 = [399666, 7111848, 34240854883018057, 159525640227776948659231897831230505709] + r15 = [399666, 7111848, 34240854883018057, 308269479959806774875048102517512730884] + + + possible_pkeys = [ + 739258514585797449032297222084055811470702691611125687711372074996687, + 460372941321907147479217537764873459531020265638440613169538863817034, + 785232755191570522054580268914288666635203565395845945113513087262967, + 506347181927680220501500584595106314695521139423160870571679876083314, + 861011580078658110931573476857568388286745404020778288869777707662969, + 582126006814767809378493792538386036347062978048093214327944496483316, + 44267527335610710524512040903173061894857656284200226876603191954338, + 628100247420540882400776839368618891511563851832813471730085508749596, + 234618045928279591028567643416009290044824769688484847665230019225315, + 818450766013209762904832441881455119661530965237098092518712336020573, + 280592286534052664050850690246242145209325643473205105067371031491595, + 1706713270162362497771005927059793269643217500520030525537820311942, + 356371111421140252927843898189521866860867482098137448823635651891597, + 77485538157249951374764213870339514921185056125452374281802440711944, + 402345352026913325950126945019754722025368355882857706225776664157877, + 123459778763023024397047260700572370085685929910172631683943452978224] + + +So we finally decrypted the public key. Now the next step is to look at the `'encrypt()'` function which uses our public key and try to reverse it. Because the first part of each encrypted bit in `'enc'` could be either `'c'` or `'p-c'`, we have to find a method to distinguish between those two cases when reversing `c = (s * g + t) % p`, where `'g'` is in this case our `'pkey'` and `'s'` and `'t'` are generated by `gen_rand()`. + +Now we can use the information I mentioned earlier that all numbers generated by the `gen_rand()` function have in their binary representation exactly five `'1'`. If we menage to reverse `c = (s * g + t) % p` to get just `'s'`, we can check if it is a valid number generated by `'gen_rand()'`. + +Trying some modulo arithmetics to inverse the expression: + + c = (s * pkey + t) % p + (c - t) ≡ s * pkey (mod p) + (c - t) * pkey ≡ s * pkey^2 (mod p) + (c - t) * pkey ≡ s * H (mod p) because H ≡ pkey^2 (mod p) + + Rule: + a ≡ b mod p + a = b + p * k + + s * H = (c - t) * pkey + p * k + s = ((c - t) * pkey + p * k) / H + +Bummer! Brute forcing `'s'` by iterating over `'k'` and checking if `'s'` is a whole integer wasn't a good idea. I tried it for k in `range(10000000)`. No solution... + +Then I spend time searching in math forums how to reverse such an expression and I found out, that I can do the following: + + c = (s * pkey + t) % p + (c - t) ≡ s * pkey (mod p) + (c - t) * pkey^(-1) ≡ s * pkey * pkey^(-1) (mod p) pkey^(-1) is modular inverse of pkey mod p + (c - t) * pkey^(-1) ≡ s * 1 (mod p) + + Rule: + The value of the modular inverse of a by the modulo n is the value a^(−1) such that aa^(−1) = 1 (mod n). It can be calculated through the "Extended Euclidean Algorithm", which finds solutions to the "Bеzout identity" (ax + by = d). + + Note: + Modular inverse of a number n mod m exists only if gcd(n,m) = 1 + The library I used "Crypto.Util.number" doesn't check this and might produce wrong answers. + Better alternatives are: "gmpy2" and "sage". + +Having now `'s'` produced by `s = ((c - t) * inverse(pkey, p)) % p` we check if it is valid. If it is valid, then it was encrypted with just `'c'` and corresponds to bit `'0'`, if it is not, then it was produced by `s = (((p - c) - t) * inverse(pkey, p)) % p` and it corresponds to bit `'1'`. + +Going through all the elements in `'enc'` we reverse the bits and reconstruct the flag = `ASIS{T0y_3XampL3_w1tH__m3rSEnN3__nUmB3r5}`. +`"Mersenne numbers"` are of the form Mn = 2^n − 1. Our `'p'` value was a mersenne number (2^229 - 1) + +The final exploit was: + +``` python +#!/usr/bin/env python3 +enc = [...] + +# Calculated via the "Tonnelli-Shanks algorithm" and the "Chinese remainder theorem" +possible_pkeys = [ +739258514585797449032297222084055811470702691611125687711372074996687, +460372941321907147479217537764873459531020265638440613169538863817034, +785232755191570522054580268914288666635203565395845945113513087262967, +506347181927680220501500584595106314695521139423160870571679876083314, +861011580078658110931573476857568388286745404020778288869777707662969, +582126006814767809378493792538386036347062978048093214327944496483316, +44267527335610710524512040903173061894857656284200226876603191954338, +628100247420540882400776839368618891511563851832813471730085508749596, +234618045928279591028567643416009290044824769688484847665230019225315, +818450766013209762904832441881455119661530965237098092518712336020573, +280592286534052664050850690246242145209325643473205105067371031491595, +1706713270162362497771005927059793269643217500520030525537820311942, +356371111421140252927843898189521866860867482098137448823635651891597, +77485538157249951374764213870339514921185056125452374281802440711944, +402345352026913325950126945019754722025368355882857706225776664157877, +123459778763023024397047260700572370085685929910172631683943452978224] + +H = 381704527450191606347421195235742637659723827441243208291869156144963 +p = 862718293348820473429344482784628181556388621521298319395315527974911 + +from Crypto.Util.number import * + +flag = '' + +# Check all possible public keys, because only one of them is used for the encryption +for pkey in possible_pkeys: + + # For each flag try to reverse its bits + for i in range(len(enc)): + c = enc[i][0] + t = enc[i][1] + + a = ((c - t) * inverse(pkey,p)) % p + x = bin(a)[2:].count('1') + if (x == 5): + flag += '0' + continue + + a = (((p - c) - t) * inverse(pkey,p)) % p + y = bin(a)[2:].count('1') + if (y == 5): + flag += '1' + continue + + # If we got a meaningful flag, reverse it. + if (flag != ''): + print(long_to_bytes(int(flag,2))) + flag = '' + +``` \ No newline at end of file diff --git a/writeups/icecrax/asis2019/chinese_remainder_theorem.py b/writeups/icecrax/asis2019/chinese_remainder_theorem.py new file mode 100644 index 0000000..490d585 --- /dev/null +++ b/writeups/icecrax/asis2019/chinese_remainder_theorem.py @@ -0,0 +1,81 @@ +from functools import reduce +def chinese_remainder(n, a): + sum = 0 + prod = reduce(lambda a, b: a*b, n) + for n_i, a_i in zip(n, a): + p = prod // n_i + sum += a_i * mul_inv(p, n_i) * p + return sum % prod + +def mul_inv(a, b): + b0 = b + x0, x1 = 0, 1 + if b == 1: return 1 + while a > 1: + q = a // b + a, b = b, a%b + x0, x1 = x1 - q * x0, x0 + if x1 < 0: x1 += b0 + return x1 + + +# Chinese Remainder Theorem: +# In number theory, the Chinese remainder theorem states that if one knows the remainders +# of the Euclidean division of an integer n by several integers, then one can determine +# uniquely the remainder of the division of n by the product of these integers, under the +# condition that the divisors are pairwise coprime. + +# What follows from the theorem: +# If M, N are coprime and A is coprime to M and N, +# then A is a quadratic residue modulo (M * N) if and only if it is a quadratic residue modulo M and modulo N +# a ≡ x^2 mod mn => a ≡ x^2 mod m and a ≡ x^2 mod n. +# H ≡ pkey^2 mod p => H ≡ pkey^2 mod p0 and H ≡ pkey^2 mod p1 ... + +# Note: +# If each factor has 2 solutions, then for H we have 2*2*2*2 = 16 solutions +# To use the theorem all factors pi should be coprime gcd(pi, pj) = 1 ! + +if __name__ == '__main__': + p = 862718293348820473429344482784628181556388621521298319395315527974911 + H = 381704527450191606347421195235742637659723827441243208291869156144963 # odd integer coprime to p + + factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593] # factors are coprime + + r0 = [1104407, 13380905, 25592602581952126, 159525640227776948659231897831230505709] + r1 = [1104407, 13380905, 25592602581952126, 308269479959806774875048102517512730884] + r2 = [1104407, 13380905, 34240854883018057, 159525640227776948659231897831230505709] + r3 = [1104407, 13380905, 34240854883018057, 308269479959806774875048102517512730884] + r4 = [1104407, 7111848, 25592602581952126, 159525640227776948659231897831230505709] + r5 = [1104407, 7111848, 25592602581952126, 308269479959806774875048102517512730884] + r6 = [1104407, 7111848, 34240854883018057, 159525640227776948659231897831230505709] + r7 = [1104407, 7111848, 34240854883018057, 308269479959806774875048102517512730884] + r8 = [399666, 13380905, 25592602581952126, 159525640227776948659231897831230505709] + r9 = [399666, 13380905, 25592602581952126, 308269479959806774875048102517512730884] + r10 = [399666, 13380905, 34240854883018057, 159525640227776948659231897831230505709] + r11 = [399666, 13380905, 34240854883018057, 308269479959806774875048102517512730884] + r12 = [399666, 7111848, 25592602581952126, 159525640227776948659231897831230505709] + r13 = [399666, 7111848, 25592602581952126, 308269479959806774875048102517512730884] + r14 = [399666, 7111848, 34240854883018057, 159525640227776948659231897831230505709] + r15 = [399666, 7111848, 34240854883018057, 308269479959806774875048102517512730884] + + rs = [r0, r1, r2, r3, r4, r5, r6, r7, r8, r9, r10, r11, r12, r13, r14, r15] + for r in rs: + print(chinese_remainder(factors, r)) + +# Results: +# 739258514585797449032297222084055811470702691611125687711372074996687 +# 460372941321907147479217537764873459531020265638440613169538863817034 +# 785232755191570522054580268914288666635203565395845945113513087262967 +# 506347181927680220501500584595106314695521139423160870571679876083314 +# 861011580078658110931573476857568388286745404020778288869777707662969 +# 582126006814767809378493792538386036347062978048093214327944496483316 +# 44267527335610710524512040903173061894857656284200226876603191954338 +# 628100247420540882400776839368618891511563851832813471730085508749596 +# 234618045928279591028567643416009290044824769688484847665230019225315 +# 818450766013209762904832441881455119661530965237098092518712336020573 +# 280592286534052664050850690246242145209325643473205105067371031491595 +# 1706713270162362497771005927059793269643217500520030525537820311942 +# 356371111421140252927843898189521866860867482098137448823635651891597 +# 77485538157249951374764213870339514921185056125452374281802440711944 +# 402345352026913325950126945019754722025368355882857706225776664157877 +# 123459778763023024397047260700572370085685929910172631683943452978224 \ No newline at end of file diff --git a/writeups/icecrax/asis2019/exploit.py b/writeups/icecrax/asis2019/exploit.py new file mode 100755 index 0000000..09a7671 --- /dev/null +++ b/writeups/icecrax/asis2019/exploit.py @@ -0,0 +1,49 @@ +enc=[(693452030319839722726551032492658894345570855091353510812978453643631,374147273652096600518280302026002167242456968463360),(688559612388766711617272277684383103592686215888250125242406607896646,1684996666696915012012216278925205994248717536439095543946901716996),(378940288706735756349711787806658208666776697748239130653541467467677,46768052395269458121440307166481563409072781262848),(96192682537252933190719942697876279568205071028966045728552811342752,1427269470777442821119947625424370788877729792),(326046970830869347127025860081671929137127663636883986249275995969665,187072209578355573854590213492815704776701722494976),(340905918585524940327083299326143363870527182200486260808937793514394,48264630071912636341289319625352763693625718863839232),(580732406123392374746863117598833633024192305365332270959719531036156,6628619432568334886610593630907295735406448532595523987702272),(343172469991113581478426010205770481485741993996461315271941164510364,1461501637330902919471340268648079110045486284864),(206357632491097972224922712046385894951738509288325125764435001713923,128555092580576529751800434855695951226303822209407977961553920),(137966355825816084773698804533858457152780009038160636654460300675342,116058059346682712221032448),(82847390600586144368056026391355099722791206361251761154749903374094,93536461601100963256273744465562705034359993274368),(751986638799289595265149536405637224204725940800743594963228860061924,16455045573212060421549691825573505049827358656335798634560225280),(802931826129070200772858720488151794540124975378515139224474511862569,2854496065976653603993498865648205136310566944),(170604347886491596997471175509943467962577432202884930761272860483899,11972621413014756705934747161492028441866746992787456),(231670999702886273678837133175491868199857203188614998695787889543779,2993155353253689176481146537402967223920928164429856),(262740536805176808265319105747071439904471636767513398787197598473855,105318719420734222659020195532372103968251413180750194740478083074),(59111720907981026936231495028158247935079956410163777060247003548083,3342431135123690854859058868786961304654117447759271246021263360),(524359127340942535772888772638206175037171324139989318704226925507324,411376237410016491331038563299276914792724526176526845444358144),(382737347874711092785046787852072485163072322578734840935304669428544,1496577676626844588240578222888927325843806520082432),(802775070731921625432464090176751008546870949864724322064281310179552,6129982163463560877951258843626323555061761964930760704),(646048910202143640361361233843656129100086655640205114578067034527695,6739986666885739663282170658689841878463818543444376235223206068224),(461504661217436737966627130744275104077308392354997153391010365241623,53946221407218419634297347994403740723578157383791790737922342256640),(680511395277606041633975136534075665239518578981319351119236462077767,2993155367191654925562786000862771553667775312429056),(850426958764423588632347567177783197647961523449837291485926496795123,822752303180531674931706325012227691848075027860388786022137856),(271426212409165947232025284582724750916571218636353120125159853917389,411376139330675655147455340973908066265912940181189757182672896),(780870488022676889507447376705241201578567745988595508291870383337207,10384613524110874118973376295862272),(597505993008546898507614382965573251099692277171605366507612840291717,1361129629943030683076085193341940023296),(434984988610836344619481991305391822903221279351821426383629066764444,748288894065285290446844488194754954167610872176640),(107978668362785379592570838755447859829216669967459102968313823416883,2056880721171436206547933211930240565633404548875915541098790912),(635701873253478471783013549228314643009208621720415113693275432556119,348491679022906103894428524344057293455360),(667408232013307737438182376251200716613746658255155809046790697764706,803469022129495137770981046170581301270546373972328078901376),(535448035764391749542080439186042777182521188323886068472078596629688,6740012377796368092511162443148385127010926460884196566465874232322),(417302118285923576760573075550964896894839401693615641598471322949124,696898287454081973172991773043997913645057),(232875801181083157087957512544200066354051448419001066249217345867241,785020840808551567695392492653530795181674979993942228992),(270677354838606142707464641833094782400400127195809856355654631975338,3213876088517980551083924184682335108564720271751285546418176),(636694663725556745506157842420089923039732711859462499990218429983336,13480024755592736185022324886296770254021872566810656027648771227648),(668999458100992846956227404787147189998236847159062284157052600227297,6427752177036052446020181550797038140390856742819899839612928),(792478061219626301734381667433772734744929272398746309874282296586483,204005818372688537839419864774983737402530863231728679387136),(14784388971069208490798380170313675093551235003366757264784996129599,3064991081731777737987262653842198174239439613042098176),(630127459026650039928817107948690698184081415449612161823297049456676,9873027343927236252929815095676410028997386962086008658876956672),(832403216671389321805675024920510434420237606267697864247364577957800,1684996666696914988262814692714975588695146812601972920444090581120),(406646182323128231888769533233788658135041685943081561702311551644733,1532495543720407382971217413082396632063092349225402368),(496617950721551213794094793580924223283906661859174693631645001916389,25108406941546724449139732600994612614854723625710566506496),(177831003286604033957623834460647192100766586594054618964739482172351,52656145834278593349137419824691109077177173039144358801651531776),(539882854946406427888058275633418591133349054394509445631347713171201,365375432471926690315941525514379272247981375488),(144151053654073090943458276500843577081962396563975572204346428496345,50216813883093446154242458351581069942313745090679431757824),(817034221076072182115853498406058894215695235157620853741013214676293,210624583337114373398690550752752784399926105553111046848182747394),(565027524911704612322247236464999223953552856140842785923178998520727,11692057700137623004371069763323117458308884070400),(44848945457110587448910039711036479247005128723275860636522988529359,11972621413036534777407565825354705909908838544310272),(502030225141450445870797796625178087582835138735804659198760982699183,822752279426874175536626314904540025023845985158977587314425856),(211732717349042334187278869176146140939337741251979099046531161250332,54762391667649737082917379970694924438481235067772969880983896588288),(523557421672885164970109383882564718066559446480130485911928330031677,383123885216472214589586756787577314351428855329202177),(71517828885363020633621213374058200326398970019294509848559261936559,208419393557760895625770937162472879800135958433552662688),(823123124991692988152469181166703931616472473732665700248772092497705,374509844742720569483596306838914213706398406017024),(605364764573169077465511002514730100031879121989322038387494273297096,3369993333393829974334804133570824408083593796723472958813064134784),(394679632316513794520913785319106658942616142197019491471497441233730,205688069667021477365154703554969539612239139752399275766579264),(829190364049686124098170725402373833439120118556532679179460958524611,52614061731505654871660551505454251247175459143680),(522016272774894591593770796695714698753549207957914373207554567783223,3369993735128347025391652278746329962918006903870250353062349635584),(473393609598717548019710325267623287467534761945536321488448784502722,196159429322188776575649117174541249870012427864410947584),(591273089355727479593423316090606868298797980477205165566222822016237,100433627766186892221372630771322662657638840032997878661376),(486531060908630269238410598966205659404039859561390246756633622194355,5575186299632655785383929569287990283927680),(114391142209060330647979314156055473287302286028347453711418267465519,421249166674276637277324256873791359380464161016617544290278572032),(858983109490912471494450183983197555834576987287645547765228438604998,10889035746541871247338054149992886566912),(325375141973271847037212512567473626085721706722474746802868027419741,6427752272816932414648681466210323285059030303545502044520448),(374724438814724119323780629462916862952472839543608185674905399743080,3138550867693340381917894711604143901986818681929920937985),(206251138555297308344727395155771670531702854857565030062123953447945,6326141592694389207308573440059615973469770324615031162896),(378047776883019597560393585680406769222353554620482409072362908381494,1496577676626844588240573268701473814379475811958792),(588639491578835232966144051762676933104027240555599097798322256513087,3138556854004046889296413827396381133152905691683960651776),(40702516581069911860733620442534271078027489772331615143136170207252,5316911983142081343263469096772042816),(840069217770815327263487792902957266779792867170272165997248134523323,39492109375708956703732359028599757749064324866653315402918002688),(116351025865567429655785962763074342160326107393119150036922900730045,215679573340343860786972069314267305485849231074146685734105886228480),(690659908415866547141500140808077318738722134032023277706462392648445,52861833903943744104228385165112980416179284906781285068153290752),(279888073845503140568351048475307270681943520940682171337009980569145,26514477730273339546442714805996104054165130796530114708373504),(49700790535908389566590757399902790802291146713376681817869728742193,324518553658426735931094911156736),(240908362329583231388225646762615116897877416314274606526084491897715,182688053115506591816466627845576879047339671552),(446555330534920211027929622967770677781513507501218890060887332139823,6427752177044730112688817144919684726873966712921226175578112),(94652945245028270771950910711933866206371205728627584849628179866653,53919893535171600112789546394501239594115119581139887685633023410176),(418747050307216945487064154224977440872249858385373606495725391503657,324518553658426727065189343035408),(176860965024736676766514941741589472749657006020585423428644026634533,13479973358683726838880944222699326009589767018664432765976152375296),(106500429354265472170550411785380480316535026114175737600478156244898,421249169812779614485012492652659517629151355821250269819703656448),(420857653269010945224642119676402828492030319375642785750885498736303,4113761393303015105387422956393386403661641489919161906875080704),(834767442657154690547265383127929771699563552670308067943029567313038,92057476264605004063445821052477609254225709056),(168977631811554775490921114532907957026333801194573708927911410083852,191561944041080764371868875106160831510959648583712768),(803973054226700963104777984588556212930117852007738740856378922988591,12855553394677564423018753090670650130782184859437083442282496),(79962340092691536257750908054300069280989663290221327095272962352052,24519928653854221744408915092465202601521719791203647488),(806011831377928463760257217966520778100222655463622861275804956383497,803469022504004932337025085113776250699172419034386565955584),(750781254420798236551979063272118994872643668028320876672284201059873,392318858461667547909878022420854320904006790452495777792),(29353240456464305550990505957315985018101002946286401717578329050753,52656145834278593348959013841835216159466890513388389698246803520),(444336794723519771373923440260674972898123335302802167236235560902763,25108406941546723055683442655900033395286610650537178169344),(60661732937705796261233561439811737107976903655877933835057454634519,54635893504805670450012853268334750850237238012060489440296960),(256297476945522999974261900190320077935619261018879923331664149237643,210624583337114747540255212079152538778999824106147273162748854272),(366458340472396746520111888623552255532605155303218633433237364185779,26973110703609209443004344043461049753669045566822849192938585456640),(800878129377096677194048665665499345974750551224591731775226417058301,12554203494157387724966025537674290155665243707022885520384),(308663415425163689096182799561147884139383285307124160990489366586528,1684996666697298111051905612051603957941082276696174715486974509056),(214907390834300670893472871879069780300832382478329842983696909750437,105312291668557187428668846349121891420892254263673351210677567490),(791995612343995232105751137767776679002181975402689717855952369330544,1427250585106079342860525522248361253787402240),(198345736375581211023110637457462977172215249403433838962498898405077,3064991081731777886857877514769850117371526033962958976),(247613364465209394623427678353241135727098882567805508935538668530753,6277101735386680763835810192395100593228694917553932210176),(658921623576357555181667346962743844469316667742927431505937254977539,1645504557464877499111146263028445538778077351597836657127064576),(740175737556671998149488283623946900309697364482092027980880872937906,324597781820940991121333680078976),(7725650152898358257254589313614602764272450761292508181897987286540,215732332327074229526062714395575490434029602459383292361288691220480),(562958397821088590782794749548439909904462633625818953588388218705508,421249179228432220488036913068066412098282898128939375104503054336),(200150547736786653188364891683269129651081310929101096435824939142969,24735435839288487354440194985097959166850749927994163200),(805222551881899063516708212519875946100475481201996888628756374664721,6427752177035961102167848410903027754398627306091120047423488),(147053410252826454195108910260623507684141616121271544655221373740332,6582018229284872398173908650036087335257164161687946125224443904),(58711757178728343806881125664232300456068326069443496214636392359237,748654213722755019849837555558915994903587418275840),(259391584033497753528529457526203076038542950756094278426468119042899,95780971304118096182733124085169717380366118223347712),(439548228723895220241811233876897411010229605184061371882248535806443,196159429961584592535319878578319931900625497742366474816),(585152364372447595244584413390788227637600365997233899697382675893536,3291410849153476831878823898175029277055360775298130290000527360),(346620463496866173470397685452389764529213135398677486437433002541670,196160925808510400714456660068315317605576825210369212416),(840530071447900858473104162651107511704353168521479719699697088950307,713623849011517061756732150327891544552505472),(109624679903192788525155292489037603996029006457543823025583651897570,1532495540865888858358509286427138396982141695318556672),(370867786647702332541954100463297951185966372968574902609256613873922,55604890000998194576500719313876275718459202514500769734149919473664),(312078523996567617320839112530299653821700266504183303968282271313533,6427752189031966630582880316102988083166936091060580397350912),(110428960963339116792081835806777727311294315619238757461043512868469,5986310709294974166426909396015549196188190421024768),(426885531755732614627183269289024277433953690627649505703827276054412,107841432176298431252403555699178974756662345394236530977985555070976),(136191498563804443048738485833542250992576057388055327054242557869910,2658455991569850635273545600217391104),(56432830570743437445884836379521005588181776233292098156001763863649,26328072917151270757438760498923512115841289793464867391727992832),(600544351562025612205622380962842434816218246466314751270583109860291,26959946667150639794667015087019630678707746823453562215055352659968),(331179674738191306896854908055370378165490871918375635696313539719390,368229904718137649313192522632103789759039537152),(509305619015217032005978548383978473053289898059696469382878251066330,25108790065431939527557752472518137076647069693898544644096),(547237840121119443001598097606715629705913969858867398799256690441536,215679573337205118357427464548490226821484885682406241026804308508704),(92953260377627286088764129023783528984350978374594863771824714495147,44688602849795543110753860921148764837642240),(23858992337313644693496045836006672521689715428292788474624871480150,1667355148462087077893881585861560076685990757680319299584),(214585710751595158782440318243136766098870217271931789922621647333877,6277101735386680785656396202013000128196162818560533464064),(678077838730055701276283770668079962425661003274484943954770469393003,2923003274688390406464272789438843875360742834176),(846598900412450404826818806219926551156279706307267995564667619006163,1895621250034029360562524498476208965200585784644849764810180530176),(814021612693326312382481135132652061054353878155594713353237256701448,383123885216472214589587073700227353000315820273827840),(746148604186474644084976796692805546432539338896603354926849728442873,215705901410122640777895816675292552583933667335938143304756020379648),(327435683211686054357523855282777510511699356202150484941960017280147,12554203470774075151517931826355861975189516701289557262336),(178507334932362970371815326010348318464830330353169503445454779777306,13479973333575319897333507548975600855486146280945889903503841689600),(368622273848572992752917602114895789531776612633792879571195001067469,102844034838596764380488894597447585964670014094984713676521472),(312006486971707927008983808811937039617936890378895323697363564812479,107839786668602559178668417160001704376815700796482361893488158572544),(551110511178866958932138908123975005130994313876499867597431391283451,53919893434734907355520922395412224425595907403093615505380193861632),(262771481213003279245315864617850919040545575237764114534596010337997,55169839471171998900900493135867455638803284719568945152),(742869501486175024973342036382719218249547637684706680168324297552525,421249166674228746791716712225079115040417111465468525035862884352),(192156721876770315993452604201993130126139345960708404501460952246336,162264228589407398400825059442696),(213302372610521372196311431769138741923500612098089025196673556836606,5986310706507378352962293074805895284645049831260288),(471117363108669121355826486305123430472270472612785393646387104381971,6427801216893268810611315836469519219982696998173260013109248),(824881502554481670590517069518902921444171632823908625246496938001753,13164036458569648337418159422047049027508738376048255581737189376),(572461430337735622750933415599733046037474500830623282458444813555364,842498333348460486738697475243610531448358792666069571778113437696),(358149048839973610034548871650996307063717060084228195553540979531423,12261460904603737711455016790471174942762603602379804672),(677505522318684372089774311075750660845945255763603775677790443590668,22300745198530623141540592824778635348017152),(558413391495121703442913877828521929933132941364952437906895648290709,822752278660603753258338542585910563284762243638620014921121792),(545935519234545608163545348857636142927818966136857346147352161794041,95780971309693239947029347535529584570430102626631680),(456493093537897325506536500605130863881085164112807809399649034852763,13479973334359957614256842638989289014719530513430942924444381741056),(421413278811304087211543836718126027828325100842038213008158094222869,2535301200456458803002063470596),(750838528604836822494210624857813494090474661289386084572538765604604,98091687236829988803926066400928696223053178125980532768),(488007852318340176078102367110466930003433681950429322383696021460177,49039857490396148133829969644270497965344036566121742336),(11035600382314541941634471795476201090356228965105458988607085970020,105312297945658922085312426254848577095577810344145416290207531008),(556128432997299354549689063694510956025280208976385249884128781936728,12554203657846284904098077219948013856121461157520950165505),(249773809225051209307281444818257264258793350366084214794498953951048,210727427372713196543903728926572838438050089770246418372342317056),(672478126778098612312972485105779057253895049288672299519495040878474,451951324947841014996176838470954459048373982376589457883168),(419165300758577135727422233987301625907739757102199024823084335903172,100434394201394910153490109204458817608092793751927712120832),(560264876386399584771054631618724243702065594056321754913768962958660,75557868264698322878596),(477906822892873921167394589700874357124334292064777334081977700982632,6582018229284917704724665908021359352618772132852568681714024448),(145710142516501564229327184989543291299563487785849166189229990093918,107839786668602559178668060348078522694866109310238990105663554723840),(189545985560009958687715038792196759682640278805042445457506134801107,6739987068522171013420076249506651654470452952090530653601359986688),(852609894488643908054908617371139608384429148569910921917809354339609,23945254244011735624262082449481253088544586591109120),(110049797875890102020717739248050771042411341398149836520437812620390,25711008708143844587077355730317584742489072454882853314887680),(574601491205902532477908573236104268002246391907654118667837210481070,95780971393321034534980525216664094380313575354793984),(629668774485410137778221457924884600918061338231865477499654020435878,53919906202359837132029618338152777453613583390701865738134316122112),(815693056191677812680535968119866514372463696632296671794012404297056,5354556135364114778898370251456768),(702172466766500275297510575418553875872473169808597019756801133867379,1628276512170006912005743716347203507594923511459610625),(259431666008760919343242631627587574395831741830527035765235515822328,12652283185388778414606513057420603220184539596443546157056),(612403775960015530523094051762609314558806369292955348029698622755851,374144619863417933835752828936872192247447251058688),(674025861181549418035935072657905411815184983128653413329425980319849,411382416432130433324295309257145374248087138587037169193320448),(173647314745780780942885742990221382429196421146561519871693898481341,105312291668557186698018381037063820123109528500958816976915922944),(325997442747138974495196997680377157706988807037271796403815685569019,803470554625036003659839405166645558887147792568884677050368),(162664278587616535859150099388857521467053919550544355614703108231736,52656147403673753410472976214194797763389412615558378305276084224),(549564800816912722871092589742310593643163870965367092706242230072098,52681856842986737924118503900764133862930321667499831575309197312),(792963569419256326206595725833756013005590046076836433258511217101179,2660942832666963607552),(432780578950996822107609049636126880338854739570444659004097625639554,3138550867693340381917894733153893411931077547680266977280),(257778156735226181447689620800810023465952928277206146875120655418966,98085700926123394313289768179125069991093380415213273088),(587065971825965834497276117203910977079556461084534960421389032953067,13164136892197414524131974834418803358309460435668846065852874752),(153192164878170826280322834862324004149008185463435598956773098485559,24519928836541926400096417209884893840549038578236129312),(156965044122930602205967892804220455758232263525424269013404942378348,107839786671741110046362827977689123366033623926687827814317203406848),(100366693820818421361420473169124924723543212365781334539472130614204,5090419188505904333333054095360),(251939620190311008486308632465949843981301562175996763754360381650960,102844034832575377634685573909834407799361621183465296924508160),(585793913500056322248801004114805246311706577029221898154184317246312,98079715346167705600385668839462213554509808252745678848),(57547440941424662625797828126439446179334837294903933366368981500041,45671926209126174318259288168669061905597333504),(670097090043641243629960502205086625671440809853895316567086108755126,3065002773745747486799357286245746337073121570752299008),(808802686685848213251846588293888457887104595073257056353657579135257,5054990000090744961500065372372323717187087902538309343273340108800),(817917169190470265630500614290094969695642629207446104037317471289599,9444733247248626896896),(33485639104872274914269380153933078806424785359602448880983379201051,13164036458569648337239753460791111078424615002065993125026856960),(7313342236662149632656437927186486545432728969806435728893059629107,23945242828817106561665579420078650338271796226162688),(237125104851650206636344380366190398542994015796551543902621757460321,6739999547400420962147099144336451769589238235424112247465691840512),(15727330822017403434040710593879822965336745210272397690125497437485,25108502734210084873534425496395624291900207403021746831368),(152322018243732677824714462662446147069529649185980769847690947054180,1267650600246676147906874974208),(535587694846859645002285298836084061025031616848911765826820401432807,2993155353253691834937217335397207714221462470524928),(753375474431791236792194973479444840075139407109930487707280335727306,1427253137223830616093044196557048120059363392),(520738115169806292098245248686439701531899619571589621728208374328821,1298232825701240346480414252105728),(564110733137782897689998891260667950237018051397301804107604775654691,6582018229284824534017586808153662193993687359877723278639398912),(619128208588374724914214565753091464289503629994595814463633725666293,431411802820244515308021200406155936379026703616076819377785445285888),(66972961307000586016823445576363508594278393405925141606178718040096,93536104789183103839278245787137387688226239545344),(854451608909880176385086168860146798519511808911687645953100642208943,95781016976044220258882070496184656874700495728410624),(253401919622819272169029582322737165205774425680374143860647565807433,3369993333393925755304681700914459276706047735999163864204630294528),(44603853363696503015926332507219992779770095018118860817519460488001,100353353434926179005189353255302334899093504),(613420674409911254282451329100656670589939752601202157710976482471189,6277197516359501332562936902270488948194691318870752362496),(125954204132922559739513583280005192817711981437646255859007009874421,1045347431181122998449835392684994808774656),(796309046335431629232667576300998618714095644059564220693372624948279,3291009261761984007792091579728247056690555679015927057001480192),(775135097709399567479904838900077705857396031454549248312972297248522,669319516920505123990280767275016),(55060545450309413853603177915191780358948246497741320787303653166693,13164036458569835409449331816032334116472237127619917417753346048),(462371489679573960089480707991549451062470285090700652816815144715813,53919893334301279589334030174039261347274443587586415922986650435584),(243150080874162088153630797570421735518201052301723433301631635639728,51422017416287688817342786955079463176510319102941444895146240),(334670203248545279741870382995308928067162629980205087861026423534033,178405961588244985151638004608951050064363520),(750732187252476709702248392595499616024973319745563515908252302579451,51422017416287688817342786957513351709977928062059242359623680),(277536582772636045425388371309279044022055523846799242144360360471112,357508821630098819361459205124143461485772800),(512939759480903024908145876148290637879841406900142400975753656579520,52656145834280089926635640686423456891173783128507030712380030976),(194619214198831424533039617315241955596493552522179040847462356114615,7404770507945427189697366766025953078040127722262434314532683776),(435773871625620285103759844375561399902552629224183767787857381595353,340282366920943300642392592944742793216),(642939069009093996886719520031484179117791830092505774384227613015416,26514477730273339546442374526225331525626268122353864309473536),(102299526284265143603028587443966228361158777671720777030190461473486,1569275620918880117763664612914562987131233001835205754880),(763338006145124397215081683878784634504069151307361922708052148574924,53919894941239419629295609834820636410698199804400707782916670750720),(344758519123883827295533591388647636306096019446969490496539001521348,6739986667572297665592943362619803650666078049242381832475482521600),(587182214153568765091953522954788782970164888400894103278189457275568,6280166820004561932220689943544079399748251477548535382016),(345471512512511593635230550463406244066356588398391453128033052472444,13479973333967638849331324481917736002051163727555342014931548504064),(534377734473264846985714340397656607073299325982489019628194423953384,53919893334302045837104463118468440520787868835966533104243344146432),(4888648147289230190071441695491941016062946099222405288225966347584,3291009114642412084310286814258428050952362819503314949462036480),(89212939965721102456116454494101259868574495969190373327984489743385,48077557861637382397238558699776748228681952877608960),(634377869717896529018919836230777743949562627114534065755260252414127,194105860432582407344420185095236186631181434880),(539723959095048896768302357495412421176854497729632997014685420009461,191561942608236277435976838877527784622926835606355968),(85310312172787768995378412605360541503887008720358055964164507726840,6153927406289584946846535355269836527287085920939933696),(321509091288328333695018223406000468185148968791626074738907896005704,6669420593848526717537114507143277852855798537763539648512),(257492089785142144909767785775108586118758919303329762406003598405116,12560333452936825083190082826254168684805605958027049041920),(365216403976412882891499358409632079289522094998041805260303737064805,309485009830352285427826692),(101107829427137840073281044154040960859343028188710336850003952634461,2787593149816327902665602795901736282226688),(815509469360154826720359307291430221723417036267369576380446046204087,10143680682199555003602750668800),(11528805133548261761735608305894472225621174205027361420784624890556,162261753918217753766757000020480),(509279878305331462729347589095015561946563624688112990865641513583612,431411802820244708366552903250649456707353887086226794684441178406912),(124684107457873578656155412469870949546705562052700839038370581629937,25108406941546723055343157702971870466235256998625858027520),(728494831413849146602851794272985815892836819287949776665655350390271,12554203470773361527671584038751805448289476091820798115840),(642774667508730866497279110575774907753677540175028494087291627873241,13164036464699630500703308893912961335897262970129774979173056512),(52771303378415527667369462942011645363492418224040078143539002664702,65820182292860214313320772829823785577342790521867597975570612224),(168359999921161326173162953349788198667365699596015639622920186790812,766247771860192121885135932410521096288428240679206920),(168226190537205276548989700578953638131386957686043333368393748730778,1645504557321206042154969182578119692416875176147842586153877568),(439921106653026494823280719533767456071576026269966414563010010327425,51422017416287688817342787619533736474368888711756444040429568),(343952219761773552415313446179978659338988164812116154581166361021021,100436692757274332990200453752951773297952778873435223752704),(61584047095535500801906745841890716733459163979148172004518799620205,215679779025274783508091568473266453304163061108282194634700551684096),(722593284768031724655303316826932088037890242183185255501093195701802,5708991121740030411450934324439073256560918536),(690716540098620497555926117445942324684737471235468774190731279336427,100433627766186892221372630771323900597676972491699619168256),(669392645886482737739390963983696451343267234713808995954303335325792,79847132533907028834802204672),(207590557461481663127669130430838606012875318174568971601125366188861,842498333348457493583345615308473662580234088526264799419357462528),(23185251238937704561141336566321976260127508485548395180737741722098,210624583337114467297316950776473120305460094781704207428654989312),(416855374894921113782534644635007663793062966491302873605993929430121,3064991081732126165860421095287204862835488375018360832),(688319696730057544754088445596458076238527401282866833093837238475987,6141954784876570190139312694750848527277820897344421888),(306432257640939953566740314651678801110886945363027160067316576346214,52669001338632671117169898862185618275007056189356896593668734976),(28860070882891509643419122889136415923962683060569552295393157681048,6582018229284835860632975377452828779048019799480172489876766720),(717502673282732523927141109893110110703666302507632555260202753552377,205688069665524899688614971252660716686663976133192686615134240),(271677332048695078514501894832048619847419552435828826896493097694650,215679573337205118404104173090745938771615070027245640981418352836624),(340878207602750073950110567367903712569510055495258262234653608939007,14167171506202973708288),(409349179571860438774186356627684012687405913335897708829320945937764,842910111222298859841451849255525881468057077721549730836006305792),(254731907946879886054764439853247238125853172568622578537763450379634,2923003274661805836724282315490343965635010101248),(718781469849041992899458319268522763144984696194268244804488188624031,401783550922240841829754963505320179236173255113699347136512),(462415089627089609600087598494132844258542679329582904614761604090736,8034690221294951377709818437073787722106399965708915534987264),(363845629546621371607202160185718064910929436586955307943481619444353,51447125824725813930648821053830547744219363759702470016630784),(97770530969287269158060544485293845143583863370700369172416983238688,1658372616644996508153776980059292031569435113732631191521067008),(484199199063386082375602803984044531817542160586182983945018620497784,100433627766187073414927368832635687635348652379361788305410),(624543205364896832580501114617745065470704120098056555538225786466600,1569275433846670190958947396366755173031509474555891548160),(477019413150617665618003038063171615565600590229503878484498285376741,107839992356672224329423329719226342363362319653285475949881883361280),(602601896256019782497554150324583346038431287659013758994880028994608,6321544106073185337303089650941371364819339401735702528),(130742071811791354747582429668771690214033136281335869055455808227786,431359148281348280973662516956054254602296974944508128356084033259520),(436361743879991020361562189290258400473853099103314964989121819262855,49039857307708465245538587809567906248605519686961987584),(117248319331773627541923295729602122697435560494918863297443464355803,803518061986802846214448513275450111174014624657750701899776),(17332146487275919066695261854531366268932336322802912039178956119365,174224613422177771175520502176582837207040),(737195875867668019457086041833004621969470322761269124025688848694321,13480024755788895614253158660166638835756369326482649289140046135328),(77265002476110899320161473772867596371641275418079147388930948766970,6277101735386680763835789423207666416106967200851206078978),(556076070203139884850582649383180450136331314789610513721545271631443,1645504557327192352867051747215137750701460518079064624727064576),(193916805648059970962590078633021629080305662599843145202733641018264,822752278660603021077484591278675886316743604795216594483545088),(517798231623699045839696359443094441562052041475768776678405923451229,421262022178582819079251857125275655811075621258715892000982433792),(267904833920988021755713804525256419760378275403162741501392437432767,6741632171344981154708908740937465018914268843861959959166259824640),(344732998585264137278518183990826817681052934281348312892269837964114,2787678220408058127307830627732903130370080),(279046200598226503025195411999556640561360813741428047435649929638887,53919896548177368107317435753348858030491248876033001444230813450240),(308870957825708469714089919616978942471477644937229563165812001499328,43558801421871693155057757365937721311264),(656771183507056771530189311265967581848842023836838155327575923027336,7231417358594709909675782579312803883500927862552389383882752),(799951954396033959301943714852765024015676508282446847398265322484737,3923188608000707249878114713577990542482597304562406653952),(23466363972826628201392499018846555677122307675763716232101471027527,31385510173511080446023535356611600781985607364393606053952),(824589189456299460272232522499712919911948713559841899842769532385981,12855896672933306875158098281404737897156577177854801971511296),(307966722179635840758817499013270716673252306547812170829528532448628,13338936968668000741204699921005642771046392163215840641024),(671864379473768418033629622516676579753429300827211122401615840347304,803469022130956639408311949088787461973896350671606510518272),(128499539598992820351912123229293324765984163573666042925341763346397,200867255555940498344706071443480706504903835121904288530432),(712003509559982421602968330751931565620423368514347115901438869479500,3291009114642413545811575696017619213650304742842199751132184576),(780537041854299422180955640564870748807158438050627610525352465330812,80880045689521584534779150595290007047821488685116114688875780112384),(84571260150626419081248266266782657358644797686276480762551836230331,1263747500022686240375016332204045187826779830506604542430113955840),(737068406434883665450664272822492309636096026307936853419320325384204,6739986666788438169058599730940792766509010872017450641534339776512),(215568957236058328757270012892331817013939468018109250548103982506604,1645504557321206042154974627075545758551810297802813790973067264),(442919351931295153592884284649535799804768603304208107000053665550219,26959946667150639888203119876388826270066001602080833955764199489536),(823839097280461907620286638920806726669356358865836126344174606896767,188533711215686517986655163459178679300685528825856),(263372892334932746977602064790619519320992768890760924624030993030214,20283648752621387104869752537088),(763875910121688864250508208444667111781012283131519186809312536280968,766247793271695105624347938400422067785374987427250688),(682914036491523349444023408643992736206940164028684625854043760847402,1606938044305758327936550985723680517471355541344305708793856),(602577396787420197341876891718840309543953979719480289760726515681434,842909709488170918979813059825945362874723168041726527707767898112),(347918673551373669515217187582448634915052644683842214774401857390286,1619493780418222719086171214737491483582140682005426183602176),(118968810066686599955040696108393709552754846084361471872892200679680,619007798574553095290748928),(795671161024590542185406750254776623283813744813188748269315213330146,65820182292848241686198767302294020199386805887021902837980364800),(791993283007778948282145743858672568728576851736939974674827204534160,1645504557321206042199570673037489134827664658359072475234435072),(782210596702728025154090078360177812742567670038536355351095315625435,26959946667150639794667015087020295287635036918256102614578801672192),(426004897768330243396894066289308407462857551899000025589634663746517,26959946668719915229975186958865623913522869182594394113142956228608),(398368568628985152651490710094105244194374545204049522269510639264300,51422017416288054192752119680646912658243703400479471800713218),(563563890988575566245652393913603597651759690958312206039998270219116,3064991081734565309866510382505213193482415091606355968),(525464830352346682976459601223775219904764050636750316674629088567014,6739986666787659948666756559390592780602373476785304363517243047936),(135513558706463057773066259572665371508964247455261100866881911077471,11417981541647699330878535932496792039632928768),(400100608844131944235138599487108082313451206959990079349829336946236,215679573337205118357336120696157045389097155418105818680695231348736),(627939359249070691809962355077312859779956827305305439060260843059047,3292616052686671074585480327290118922304551176317439256909840384),(609101544270764154186438061220538529142570406006769264465410596734497,26959946667150642787822368340708807154784300795507839989540861263872),(652479175682481292003487147179512158254161340957990062502917841738119,548063113999088614608791425365009522057524805632),(276871809952965379561635690462590116672831143556615477648135559499170,183044516589539354745725175581898032716063982080),(604745481173797027809076390394748598686088811473398911842410798005338,365375409375344102205389154611181237580993658896),(465957550610728563634565551731915228952481858309064143421092313179927,414590015418819491089826219844789138884867682910082541119602704),(488703425926869751072175591084400239373182393927063363976097237406745,47890485652059027488312342568276350895606870134751232),(390120392235291617234383444979638398579337170483373637166452197279698,51422017417784266493969631543157776549449748545181839815344128),(653100791680244527999303425412530505740256299399090672392168205373793,187894304249354206421561231306087136277465780977665),(193262532464346240505953723065267591703248895726262392292664451223698,107839786668602559178668061044998077796563110121582856664971990794240),(107045793911947398136197105188293300699239666683373268395539891241589,1464356132721631751216591668375026639666589728768),(523012293529248077643701888156084275077815953025269036072647383210035,46768052394588898899333326840175411942642467995648),(622157257340377525245646024844470880621191809662103051590357979385054,401734511064747568885490689243860726145947788034771106398208),(316313718202282856322693032620188751154014552879090456430616940216284,1684997470165937864956373518112891047494490282124986733440572325888),(584739191018300307347039255066505921203948794043447580870443268686716,786170212464200984337832024928147296822640855405965606912),(783460519482638997081925507192876069457386478570448084824250091133087,561216629431965009342371163569750782700765623353344),(388114081291408893064038973703219574667554554439776426575952568038973,356811925834945961834403238170058273434107905),(409926396074512569171554146069999496317045410843190221223641176833912,210624583435241978498332249021804732601066711684135124654509522944),(111580650341887778146995012026026650925860443325513704063610271717604,25711204870566233450194337934278985553248450736212014274707456),(544049943500270738871790342149343930450085433867843205576488089535164,103621218491187941046757992587795305759564664520750816821249),(487731884289323500594412232131366798086816624309721524464898466942517,12603243328081783594985398931224671869065811749175618961408),(514337490313840329117544989549543721439299793294549724880811538969016,365375409332725730189698268487220464909350354944),(840436795151657314984517695610620173725667736230343246728369440559566,201698643933206250391156973202602652673610826645504),(78166235150270483621568408887054775150313094818439116837713274271947,5868842515129166047418721549004285598248197947392)] + +possible_pkeys = [ +739258514585797449032297222084055811470702691611125687711372074996687, +460372941321907147479217537764873459531020265638440613169538863817034, +785232755191570522054580268914288666635203565395845945113513087262967, +506347181927680220501500584595106314695521139423160870571679876083314, +861011580078658110931573476857568388286745404020778288869777707662969, +582126006814767809378493792538386036347062978048093214327944496483316, +44267527335610710524512040903173061894857656284200226876603191954338, +628100247420540882400776839368618891511563851832813471730085508749596, +234618045928279591028567643416009290044824769688484847665230019225315, +818450766013209762904832441881455119661530965237098092518712336020573, +280592286534052664050850690246242145209325643473205105067371031491595, +1706713270162362497771005927059793269643217500520030525537820311942, +356371111421140252927843898189521866860867482098137448823635651891597, +77485538157249951374764213870339514921185056125452374281802440711944, +402345352026913325950126945019754722025368355882857706225776664157877, +123459778763023024397047260700572370085685929910172631683943452978224] + +H = 381704527450191606347421195235742637659723827441243208291869156144963 +p = 862718293348820473429344482784628181556388621521298319395315527974911 +l = 5 + +from Crypto.Util.number import * + +flag = '' + +for pkey in possible_pkeys: + + for i in range(len(enc)): + c = enc[i][0] + t = enc[i][1] + + a = ((c-t) * inverse(pkey, p)) % p + x = bin(a)[2:].count('1') + if (x == 5): + flag += '0' + continue + + a = ((p-c-t) * inverse(pkey, p)) % p + y = bin(a)[2:].count('1') + if (y == 5): + flag += '1' + continue + + if (flag != ''): + print(long_to_bytes(int(flag,2))) + flag = '' \ No newline at end of file diff --git a/writeups/icecrax/asis2019/output.txt b/writeups/icecrax/asis2019/output.txt new file mode 100644 index 0000000..fa1c346 --- /dev/null +++ b/writeups/icecrax/asis2019/output.txt @@ -0,0 +1,2 @@ +H = 381704527450191606347421195235742637659723827441243208291869156144963 +enc = [(693452030319839722726551032492658894345570855091353510812978453643631 374147273652096600518280302026002167242456968463360, (688559612388766711617272277684383103592686215888250125242406607896646 1684996666696915012012216278925205994248717536439095543946901716996, (378940288706735756349711787806658208666776697748239130653541467467677 46768052395269458121440307166481563409072781262848, (96192682537252933190719942697876279568205071028966045728552811342752 1427269470777442821119947625424370788877729792, (326046970830869347127025860081671929137127663636883986249275995969665 187072209578355573854590213492815704776701722494976, (340905918585524940327083299326143363870527182200486260808937793514394 48264630071912636341289319625352763693625718863839232, (580732406123392374746863117598833633024192305365332270959719531036156 6628619432568334886610593630907295735406448532595523987702272, (343172469991113581478426010205770481485741993996461315271941164510364 1461501637330902919471340268648079110045486284864, (206357632491097972224922712046385894951738509288325125764435001713923 128555092580576529751800434855695951226303822209407977961553920, (137966355825816084773698804533858457152780009038160636654460300675342 116058059346682712221032448, (82847390600586144368056026391355099722791206361251761154749903374094 93536461601100963256273744465562705034359993274368, (751986638799289595265149536405637224204725940800743594963228860061924 16455045573212060421549691825573505049827358656335798634560225280, (802931826129070200772858720488151794540124975378515139224474511862569 2854496065976653603993498865648205136310566944, (170604347886491596997471175509943467962577432202884930761272860483899 11972621413014756705934747161492028441866746992787456, (231670999702886273678837133175491868199857203188614998695787889543779 2993155353253689176481146537402967223920928164429856, (262740536805176808265319105747071439904471636767513398787197598473855 105318719420734222659020195532372103968251413180750194740478083074, (59111720907981026936231495028158247935079956410163777060247003548083 3342431135123690854859058868786961304654117447759271246021263360, (524359127340942535772888772638206175037171324139989318704226925507324 411376237410016491331038563299276914792724526176526845444358144, (382737347874711092785046787852072485163072322578734840935304669428544 1496577676626844588240578222888927325843806520082432, (802775070731921625432464090176751008546870949864724322064281310179552 6129982163463560877951258843626323555061761964930760704, (646048910202143640361361233843656129100086655640205114578067034527695 6739986666885739663282170658689841878463818543444376235223206068224, (461504661217436737966627130744275104077308392354997153391010365241623 53946221407218419634297347994403740723578157383791790737922342256640, (680511395277606041633975136534075665239518578981319351119236462077767 2993155367191654925562786000862771553667775312429056, (850426958764423588632347567177783197647961523449837291485926496795123 822752303180531674931706325012227691848075027860388786022137856, (271426212409165947232025284582724750916571218636353120125159853917389 411376139330675655147455340973908066265912940181189757182672896, (780870488022676889507447376705241201578567745988595508291870383337207 10384613524110874118973376295862272, (597505993008546898507614382965573251099692277171605366507612840291717 1361129629943030683076085193341940023296, (434984988610836344619481991305391822903221279351821426383629066764444 748288894065285290446844488194754954167610872176640, (107978668362785379592570838755447859829216669967459102968313823416883 2056880721171436206547933211930240565633404548875915541098790912, (635701873253478471783013549228314643009208621720415113693275432556119 348491679022906103894428524344057293455360, (667408232013307737438182376251200716613746658255155809046790697764706 803469022129495137770981046170581301270546373972328078901376, (535448035764391749542080439186042777182521188323886068472078596629688 6740012377796368092511162443148385127010926460884196566465874232322, (417302118285923576760573075550964896894839401693615641598471322949124 696898287454081973172991773043997913645057, (232875801181083157087957512544200066354051448419001066249217345867241 785020840808551567695392492653530795181674979993942228992, (270677354838606142707464641833094782400400127195809856355654631975338 3213876088517980551083924184682335108564720271751285546418176, (636694663725556745506157842420089923039732711859462499990218429983336 13480024755592736185022324886296770254021872566810656027648771227648, (668999458100992846956227404787147189998236847159062284157052600227297 6427752177036052446020181550797038140390856742819899839612928, (792478061219626301734381667433772734744929272398746309874282296586483 204005818372688537839419864774983737402530863231728679387136, (14784388971069208490798380170313675093551235003366757264784996129599 3064991081731777737987262653842198174239439613042098176, (630127459026650039928817107948690698184081415449612161823297049456676 9873027343927236252929815095676410028997386962086008658876956672, (832403216671389321805675024920510434420237606267697864247364577957800 1684996666696914988262814692714975588695146812601972920444090581120, (406646182323128231888769533233788658135041685943081561702311551644733 1532495543720407382971217413082396632063092349225402368, (496617950721551213794094793580924223283906661859174693631645001916389 25108406941546724449139732600994612614854723625710566506496, (177831003286604033957623834460647192100766586594054618964739482172351 52656145834278593349137419824691109077177173039144358801651531776, (539882854946406427888058275633418591133349054394509445631347713171201 365375432471926690315941525514379272247981375488, (144151053654073090943458276500843577081962396563975572204346428496345 50216813883093446154242458351581069942313745090679431757824, (817034221076072182115853498406058894215695235157620853741013214676293 210624583337114373398690550752752784399926105553111046848182747394, (565027524911704612322247236464999223953552856140842785923178998520727 11692057700137623004371069763323117458308884070400, (44848945457110587448910039711036479247005128723275860636522988529359 11972621413036534777407565825354705909908838544310272, (502030225141450445870797796625178087582835138735804659198760982699183 822752279426874175536626314904540025023845985158977587314425856, (211732717349042334187278869176146140939337741251979099046531161250332 54762391667649737082917379970694924438481235067772969880983896588288, (523557421672885164970109383882564718066559446480130485911928330031677 383123885216472214589586756787577314351428855329202177, (71517828885363020633621213374058200326398970019294509848559261936559 208419393557760895625770937162472879800135958433552662688, (823123124991692988152469181166703931616472473732665700248772092497705 374509844742720569483596306838914213706398406017024, (605364764573169077465511002514730100031879121989322038387494273297096 3369993333393829974334804133570824408083593796723472958813064134784, (394679632316513794520913785319106658942616142197019491471497441233730 205688069667021477365154703554969539612239139752399275766579264, (829190364049686124098170725402373833439120118556532679179460958524611 52614061731505654871660551505454251247175459143680, (522016272774894591593770796695714698753549207957914373207554567783223 3369993735128347025391652278746329962918006903870250353062349635584, (473393609598717548019710325267623287467534761945536321488448784502722 196159429322188776575649117174541249870012427864410947584, (591273089355727479593423316090606868298797980477205165566222822016237 100433627766186892221372630771322662657638840032997878661376, (486531060908630269238410598966205659404039859561390246756633622194355 5575186299632655785383929569287990283927680, (114391142209060330647979314156055473287302286028347453711418267465519 421249166674276637277324256873791359380464161016617544290278572032, (858983109490912471494450183983197555834576987287645547765228438604998 10889035746541871247338054149992886566912, (325375141973271847037212512567473626085721706722474746802868027419741 6427752272816932414648681466210323285059030303545502044520448, (374724438814724119323780629462916862952472839543608185674905399743080 3138550867693340381917894711604143901986818681929920937985, (206251138555297308344727395155771670531702854857565030062123953447945 6326141592694389207308573440059615973469770324615031162896, (378047776883019597560393585680406769222353554620482409072362908381494 1496577676626844588240573268701473814379475811958792, (588639491578835232966144051762676933104027240555599097798322256513087 3138556854004046889296413827396381133152905691683960651776, (40702516581069911860733620442534271078027489772331615143136170207252 5316911983142081343263469096772042816, (840069217770815327263487792902957266779792867170272165997248134523323 39492109375708956703732359028599757749064324866653315402918002688, (116351025865567429655785962763074342160326107393119150036922900730045 215679573340343860786972069314267305485849231074146685734105886228480, (690659908415866547141500140808077318738722134032023277706462392648445 52861833903943744104228385165112980416179284906781285068153290752, (279888073845503140568351048475307270681943520940682171337009980569145 26514477730273339546442714805996104054165130796530114708373504, (49700790535908389566590757399902790802291146713376681817869728742193 324518553658426735931094911156736, (240908362329583231388225646762615116897877416314274606526084491897715 182688053115506591816466627845576879047339671552, (446555330534920211027929622967770677781513507501218890060887332139823 6427752177044730112688817144919684726873966712921226175578112, (94652945245028270771950910711933866206371205728627584849628179866653 53919893535171600112789546394501239594115119581139887685633023410176, (418747050307216945487064154224977440872249858385373606495725391503657 324518553658426727065189343035408, (176860965024736676766514941741589472749657006020585423428644026634533 13479973358683726838880944222699326009589767018664432765976152375296, (106500429354265472170550411785380480316535026114175737600478156244898 421249169812779614485012492652659517629151355821250269819703656448, (420857653269010945224642119676402828492030319375642785750885498736303 4113761393303015105387422956393386403661641489919161906875080704, (834767442657154690547265383127929771699563552670308067943029567313038 92057476264605004063445821052477609254225709056, (168977631811554775490921114532907957026333801194573708927911410083852 191561944041080764371868875106160831510959648583712768, (803973054226700963104777984588556212930117852007738740856378922988591 12855553394677564423018753090670650130782184859437083442282496, (79962340092691536257750908054300069280989663290221327095272962352052 24519928653854221744408915092465202601521719791203647488, (806011831377928463760257217966520778100222655463622861275804956383497 803469022504004932337025085113776250699172419034386565955584, (750781254420798236551979063272118994872643668028320876672284201059873 392318858461667547909878022420854320904006790452495777792, (29353240456464305550990505957315985018101002946286401717578329050753 52656145834278593348959013841835216159466890513388389698246803520, (444336794723519771373923440260674972898123335302802167236235560902763 25108406941546723055683442655900033395286610650537178169344, (60661732937705796261233561439811737107976903655877933835057454634519 54635893504805670450012853268334750850237238012060489440296960, (256297476945522999974261900190320077935619261018879923331664149237643 210624583337114747540255212079152538778999824106147273162748854272, (366458340472396746520111888623552255532605155303218633433237364185779 26973110703609209443004344043461049753669045566822849192938585456640, (800878129377096677194048665665499345974750551224591731775226417058301 12554203494157387724966025537674290155665243707022885520384, (308663415425163689096182799561147884139383285307124160990489366586528 1684996666697298111051905612051603957941082276696174715486974509056, (214907390834300670893472871879069780300832382478329842983696909750437 105312291668557187428668846349121891420892254263673351210677567490, (791995612343995232105751137767776679002181975402689717855952369330544 1427250585106079342860525522248361253787402240, (198345736375581211023110637457462977172215249403433838962498898405077 3064991081731777886857877514769850117371526033962958976, (247613364465209394623427678353241135727098882567805508935538668530753 6277101735386680763835810192395100593228694917553932210176, (658921623576357555181667346962743844469316667742927431505937254977539 1645504557464877499111146263028445538778077351597836657127064576, (740175737556671998149488283623946900309697364482092027980880872937906 324597781820940991121333680078976, (7725650152898358257254589313614602764272450761292508181897987286540 215732332327074229526062714395575490434029602459383292361288691220480, (562958397821088590782794749548439909904462633625818953588388218705508 421249179228432220488036913068066412098282898128939375104503054336, (200150547736786653188364891683269129651081310929101096435824939142969 24735435839288487354440194985097959166850749927994163200, (805222551881899063516708212519875946100475481201996888628756374664721 6427752177035961102167848410903027754398627306091120047423488, (147053410252826454195108910260623507684141616121271544655221373740332 6582018229284872398173908650036087335257164161687946125224443904, (58711757178728343806881125664232300456068326069443496214636392359237 748654213722755019849837555558915994903587418275840, (259391584033497753528529457526203076038542950756094278426468119042899 95780971304118096182733124085169717380366118223347712, (439548228723895220241811233876897411010229605184061371882248535806443 196159429961584592535319878578319931900625497742366474816, (585152364372447595244584413390788227637600365997233899697382675893536 3291410849153476831878823898175029277055360775298130290000527360, (346620463496866173470397685452389764529213135398677486437433002541670 196160925808510400714456660068315317605576825210369212416, (840530071447900858473104162651107511704353168521479719699697088950307 713623849011517061756732150327891544552505472, (109624679903192788525155292489037603996029006457543823025583651897570 1532495540865888858358509286427138396982141695318556672, (370867786647702332541954100463297951185966372968574902609256613873922 55604890000998194576500719313876275718459202514500769734149919473664, (312078523996567617320839112530299653821700266504183303968282271313533 6427752189031966630582880316102988083166936091060580397350912, (110428960963339116792081835806777727311294315619238757461043512868469 5986310709294974166426909396015549196188190421024768, (426885531755732614627183269289024277433953690627649505703827276054412 107841432176298431252403555699178974756662345394236530977985555070976, (136191498563804443048738485833542250992576057388055327054242557869910 2658455991569850635273545600217391104, (56432830570743437445884836379521005588181776233292098156001763863649 26328072917151270757438760498923512115841289793464867391727992832, (600544351562025612205622380962842434816218246466314751270583109860291 26959946667150639794667015087019630678707746823453562215055352659968, (331179674738191306896854908055370378165490871918375635696313539719390 368229904718137649313192522632103789759039537152, (509305619015217032005978548383978473053289898059696469382878251066330 25108790065431939527557752472518137076647069693898544644096, (547237840121119443001598097606715629705913969858867398799256690441536 215679573337205118357427464548490226821484885682406241026804308508704, (92953260377627286088764129023783528984350978374594863771824714495147 44688602849795543110753860921148764837642240, (23858992337313644693496045836006672521689715428292788474624871480150 1667355148462087077893881585861560076685990757680319299584, (214585710751595158782440318243136766098870217271931789922621647333877 6277101735386680785656396202013000128196162818560533464064, (678077838730055701276283770668079962425661003274484943954770469393003 2923003274688390406464272789438843875360742834176, (846598900412450404826818806219926551156279706307267995564667619006163 1895621250034029360562524498476208965200585784644849764810180530176, (814021612693326312382481135132652061054353878155594713353237256701448 383123885216472214589587073700227353000315820273827840, (746148604186474644084976796692805546432539338896603354926849728442873 215705901410122640777895816675292552583933667335938143304756020379648, (327435683211686054357523855282777510511699356202150484941960017280147 12554203470774075151517931826355861975189516701289557262336, (178507334932362970371815326010348318464830330353169503445454779777306 13479973333575319897333507548975600855486146280945889903503841689600, (368622273848572992752917602114895789531776612633792879571195001067469 102844034838596764380488894597447585964670014094984713676521472, (312006486971707927008983808811937039617936890378895323697363564812479 107839786668602559178668417160001704376815700796482361893488158572544, (551110511178866958932138908123975005130994313876499867597431391283451 53919893434734907355520922395412224425595907403093615505380193861632, (262771481213003279245315864617850919040545575237764114534596010337997 55169839471171998900900493135867455638803284719568945152, (742869501486175024973342036382719218249547637684706680168324297552525 421249166674228746791716712225079115040417111465468525035862884352, (192156721876770315993452604201993130126139345960708404501460952246336 162264228589407398400825059442696, (213302372610521372196311431769138741923500612098089025196673556836606 5986310706507378352962293074805895284645049831260288, (471117363108669121355826486305123430472270472612785393646387104381971 6427801216893268810611315836469519219982696998173260013109248, (824881502554481670590517069518902921444171632823908625246496938001753 13164036458569648337418159422047049027508738376048255581737189376, (572461430337735622750933415599733046037474500830623282458444813555364 842498333348460486738697475243610531448358792666069571778113437696, (358149048839973610034548871650996307063717060084228195553540979531423 12261460904603737711455016790471174942762603602379804672, (677505522318684372089774311075750660845945255763603775677790443590668 22300745198530623141540592824778635348017152, (558413391495121703442913877828521929933132941364952437906895648290709 822752278660603753258338542585910563284762243638620014921121792, (545935519234545608163545348857636142927818966136857346147352161794041 95780971309693239947029347535529584570430102626631680, (456493093537897325506536500605130863881085164112807809399649034852763 13479973334359957614256842638989289014719530513430942924444381741056, (421413278811304087211543836718126027828325100842038213008158094222869 2535301200456458803002063470596, (750838528604836822494210624857813494090474661289386084572538765604604 98091687236829988803926066400928696223053178125980532768, (488007852318340176078102367110466930003433681950429322383696021460177 49039857490396148133829969644270497965344036566121742336, (11035600382314541941634471795476201090356228965105458988607085970020 105312297945658922085312426254848577095577810344145416290207531008, (556128432997299354549689063694510956025280208976385249884128781936728 12554203657846284904098077219948013856121461157520950165505, (249773809225051209307281444818257264258793350366084214794498953951048 210727427372713196543903728926572838438050089770246418372342317056, (672478126778098612312972485105779057253895049288672299519495040878474 451951324947841014996176838470954459048373982376589457883168, (419165300758577135727422233987301625907739757102199024823084335903172 100434394201394910153490109204458817608092793751927712120832, (560264876386399584771054631618724243702065594056321754913768962958660 75557868264698322878596, (477906822892873921167394589700874357124334292064777334081977700982632 6582018229284917704724665908021359352618772132852568681714024448, (145710142516501564229327184989543291299563487785849166189229990093918 107839786668602559178668060348078522694866109310238990105663554723840, (189545985560009958687715038792196759682640278805042445457506134801107 6739987068522171013420076249506651654470452952090530653601359986688, (852609894488643908054908617371139608384429148569910921917809354339609 23945254244011735624262082449481253088544586591109120, (110049797875890102020717739248050771042411341398149836520437812620390 25711008708143844587077355730317584742489072454882853314887680, (574601491205902532477908573236104268002246391907654118667837210481070 95780971393321034534980525216664094380313575354793984, (629668774485410137778221457924884600918061338231865477499654020435878 53919906202359837132029618338152777453613583390701865738134316122112, (815693056191677812680535968119866514372463696632296671794012404297056 5354556135364114778898370251456768, (702172466766500275297510575418553875872473169808597019756801133867379 1628276512170006912005743716347203507594923511459610625, (259431666008760919343242631627587574395831741830527035765235515822328 12652283185388778414606513057420603220184539596443546157056, (612403775960015530523094051762609314558806369292955348029698622755851 374144619863417933835752828936872192247447251058688, (674025861181549418035935072657905411815184983128653413329425980319849 411382416432130433324295309257145374248087138587037169193320448, (173647314745780780942885742990221382429196421146561519871693898481341 105312291668557186698018381037063820123109528500958816976915922944, (325997442747138974495196997680377157706988807037271796403815685569019 803470554625036003659839405166645558887147792568884677050368, (162664278587616535859150099388857521467053919550544355614703108231736 52656147403673753410472976214194797763389412615558378305276084224, (549564800816912722871092589742310593643163870965367092706242230072098 52681856842986737924118503900764133862930321667499831575309197312, (792963569419256326206595725833756013005590046076836433258511217101179 2660942832666963607552, (432780578950996822107609049636126880338854739570444659004097625639554 3138550867693340381917894733153893411931077547680266977280, (257778156735226181447689620800810023465952928277206146875120655418966 98085700926123394313289768179125069991093380415213273088, (587065971825965834497276117203910977079556461084534960421389032953067 13164136892197414524131974834418803358309460435668846065852874752, (153192164878170826280322834862324004149008185463435598956773098485559 24519928836541926400096417209884893840549038578236129312, (156965044122930602205967892804220455758232263525424269013404942378348 107839786671741110046362827977689123366033623926687827814317203406848, (100366693820818421361420473169124924723543212365781334539472130614204 5090419188505904333333054095360, (251939620190311008486308632465949843981301562175996763754360381650960 102844034832575377634685573909834407799361621183465296924508160, (585793913500056322248801004114805246311706577029221898154184317246312 98079715346167705600385668839462213554509808252745678848, (57547440941424662625797828126439446179334837294903933366368981500041 45671926209126174318259288168669061905597333504, (670097090043641243629960502205086625671440809853895316567086108755126 3065002773745747486799357286245746337073121570752299008, (808802686685848213251846588293888457887104595073257056353657579135257 5054990000090744961500065372372323717187087902538309343273340108800, (817917169190470265630500614290094969695642629207446104037317471289599 9444733247248626896896, (33485639104872274914269380153933078806424785359602448880983379201051 13164036458569648337239753460791111078424615002065993125026856960, (7313342236662149632656437927186486545432728969806435728893059629107 23945242828817106561665579420078650338271796226162688, (237125104851650206636344380366190398542994015796551543902621757460321 6739999547400420962147099144336451769589238235424112247465691840512, (15727330822017403434040710593879822965336745210272397690125497437485 25108502734210084873534425496395624291900207403021746831368, (152322018243732677824714462662446147069529649185980769847690947054180 1267650600246676147906874974208, (535587694846859645002285298836084061025031616848911765826820401432807 2993155353253691834937217335397207714221462470524928, (753375474431791236792194973479444840075139407109930487707280335727306 1427253137223830616093044196557048120059363392, (520738115169806292098245248686439701531899619571589621728208374328821 1298232825701240346480414252105728, (564110733137782897689998891260667950237018051397301804107604775654691 6582018229284824534017586808153662193993687359877723278639398912, (619128208588374724914214565753091464289503629994595814463633725666293 431411802820244515308021200406155936379026703616076819377785445285888, (66972961307000586016823445576363508594278393405925141606178718040096 93536104789183103839278245787137387688226239545344, (854451608909880176385086168860146798519511808911687645953100642208943 95781016976044220258882070496184656874700495728410624, (253401919622819272169029582322737165205774425680374143860647565807433 3369993333393925755304681700914459276706047735999163864204630294528, (44603853363696503015926332507219992779770095018118860817519460488001 100353353434926179005189353255302334899093504, (613420674409911254282451329100656670589939752601202157710976482471189 6277197516359501332562936902270488948194691318870752362496, (125954204132922559739513583280005192817711981437646255859007009874421 1045347431181122998449835392684994808774656, (796309046335431629232667576300998618714095644059564220693372624948279 3291009261761984007792091579728247056690555679015927057001480192, (775135097709399567479904838900077705857396031454549248312972297248522 669319516920505123990280767275016, (55060545450309413853603177915191780358948246497741320787303653166693 13164036458569835409449331816032334116472237127619917417753346048, (462371489679573960089480707991549451062470285090700652816815144715813 53919893334301279589334030174039261347274443587586415922986650435584, (243150080874162088153630797570421735518201052301723433301631635639728 51422017416287688817342786955079463176510319102941444895146240, (334670203248545279741870382995308928067162629980205087861026423534033 178405961588244985151638004608951050064363520, (750732187252476709702248392595499616024973319745563515908252302579451 51422017416287688817342786957513351709977928062059242359623680, (277536582772636045425388371309279044022055523846799242144360360471112 357508821630098819361459205124143461485772800, (512939759480903024908145876148290637879841406900142400975753656579520 52656145834280089926635640686423456891173783128507030712380030976, (194619214198831424533039617315241955596493552522179040847462356114615 7404770507945427189697366766025953078040127722262434314532683776, (435773871625620285103759844375561399902552629224183767787857381595353 340282366920943300642392592944742793216, (642939069009093996886719520031484179117791830092505774384227613015416 26514477730273339546442374526225331525626268122353864309473536, (102299526284265143603028587443966228361158777671720777030190461473486 1569275620918880117763664612914562987131233001835205754880, (763338006145124397215081683878784634504069151307361922708052148574924 53919894941239419629295609834820636410698199804400707782916670750720, (344758519123883827295533591388647636306096019446969490496539001521348 6739986667572297665592943362619803650666078049242381832475482521600, (587182214153568765091953522954788782970164888400894103278189457275568 6280166820004561932220689943544079399748251477548535382016, (345471512512511593635230550463406244066356588398391453128033052472444 13479973333967638849331324481917736002051163727555342014931548504064, (534377734473264846985714340397656607073299325982489019628194423953384 53919893334302045837104463118468440520787868835966533104243344146432, (4888648147289230190071441695491941016062946099222405288225966347584 3291009114642412084310286814258428050952362819503314949462036480, (89212939965721102456116454494101259868574495969190373327984489743385 48077557861637382397238558699776748228681952877608960, (634377869717896529018919836230777743949562627114534065755260252414127 194105860432582407344420185095236186631181434880, (539723959095048896768302357495412421176854497729632997014685420009461 191561942608236277435976838877527784622926835606355968, (85310312172787768995378412605360541503887008720358055964164507726840 6153927406289584946846535355269836527287085920939933696, (321509091288328333695018223406000468185148968791626074738907896005704 6669420593848526717537114507143277852855798537763539648512, (257492089785142144909767785775108586118758919303329762406003598405116 12560333452936825083190082826254168684805605958027049041920, (365216403976412882891499358409632079289522094998041805260303737064805 309485009830352285427826692, (101107829427137840073281044154040960859343028188710336850003952634461 2787593149816327902665602795901736282226688, (815509469360154826720359307291430221723417036267369576380446046204087 10143680682199555003602750668800, (11528805133548261761735608305894472225621174205027361420784624890556 162261753918217753766757000020480, (509279878305331462729347589095015561946563624688112990865641513583612 431411802820244708366552903250649456707353887086226794684441178406912, (124684107457873578656155412469870949546705562052700839038370581629937 25108406941546723055343157702971870466235256998625858027520, (728494831413849146602851794272985815892836819287949776665655350390271 12554203470773361527671584038751805448289476091820798115840, (642774667508730866497279110575774907753677540175028494087291627873241 13164036464699630500703308893912961335897262970129774979173056512, (52771303378415527667369462942011645363492418224040078143539002664702 65820182292860214313320772829823785577342790521867597975570612224, (168359999921161326173162953349788198667365699596015639622920186790812 766247771860192121885135932410521096288428240679206920, (168226190537205276548989700578953638131386957686043333368393748730778 1645504557321206042154969182578119692416875176147842586153877568, (439921106653026494823280719533767456071576026269966414563010010327425 51422017416287688817342787619533736474368888711756444040429568, (343952219761773552415313446179978659338988164812116154581166361021021 100436692757274332990200453752951773297952778873435223752704, (61584047095535500801906745841890716733459163979148172004518799620205 215679779025274783508091568473266453304163061108282194634700551684096, (722593284768031724655303316826932088037890242183185255501093195701802 5708991121740030411450934324439073256560918536, (690716540098620497555926117445942324684737471235468774190731279336427 100433627766186892221372630771323900597676972491699619168256, (669392645886482737739390963983696451343267234713808995954303335325792 79847132533907028834802204672, (207590557461481663127669130430838606012875318174568971601125366188861 842498333348457493583345615308473662580234088526264799419357462528, (23185251238937704561141336566321976260127508485548395180737741722098 210624583337114467297316950776473120305460094781704207428654989312, (416855374894921113782534644635007663793062966491302873605993929430121 3064991081732126165860421095287204862835488375018360832, (688319696730057544754088445596458076238527401282866833093837238475987 6141954784876570190139312694750848527277820897344421888, (306432257640939953566740314651678801110886945363027160067316576346214 52669001338632671117169898862185618275007056189356896593668734976, (28860070882891509643419122889136415923962683060569552295393157681048 6582018229284835860632975377452828779048019799480172489876766720, (717502673282732523927141109893110110703666302507632555260202753552377 205688069665524899688614971252660716686663976133192686615134240, (271677332048695078514501894832048619847419552435828826896493097694650 215679573337205118404104173090745938771615070027245640981418352836624, (340878207602750073950110567367903712569510055495258262234653608939007 14167171506202973708288, (409349179571860438774186356627684012687405913335897708829320945937764 842910111222298859841451849255525881468057077721549730836006305792, (254731907946879886054764439853247238125853172568622578537763450379634 2923003274661805836724282315490343965635010101248, (718781469849041992899458319268522763144984696194268244804488188624031 401783550922240841829754963505320179236173255113699347136512, (462415089627089609600087598494132844258542679329582904614761604090736 8034690221294951377709818437073787722106399965708915534987264, (363845629546621371607202160185718064910929436586955307943481619444353 51447125824725813930648821053830547744219363759702470016630784, (97770530969287269158060544485293845143583863370700369172416983238688 1658372616644996508153776980059292031569435113732631191521067008, (484199199063386082375602803984044531817542160586182983945018620497784 100433627766187073414927368832635687635348652379361788305410, (624543205364896832580501114617745065470704120098056555538225786466600 1569275433846670190958947396366755173031509474555891548160, (477019413150617665618003038063171615565600590229503878484498285376741 107839992356672224329423329719226342363362319653285475949881883361280, (602601896256019782497554150324583346038431287659013758994880028994608 6321544106073185337303089650941371364819339401735702528, (130742071811791354747582429668771690214033136281335869055455808227786 431359148281348280973662516956054254602296974944508128356084033259520, (436361743879991020361562189290258400473853099103314964989121819262855 49039857307708465245538587809567906248605519686961987584, (117248319331773627541923295729602122697435560494918863297443464355803 803518061986802846214448513275450111174014624657750701899776, (17332146487275919066695261854531366268932336322802912039178956119365 174224613422177771175520502176582837207040, (737195875867668019457086041833004621969470322761269124025688848694321 13480024755788895614253158660166638835756369326482649289140046135328, (77265002476110899320161473772867596371641275418079147388930948766970 6277101735386680763835789423207666416106967200851206078978, (556076070203139884850582649383180450136331314789610513721545271631443 1645504557327192352867051747215137750701460518079064624727064576, (193916805648059970962590078633021629080305662599843145202733641018264 822752278660603021077484591278675886316743604795216594483545088, (517798231623699045839696359443094441562052041475768776678405923451229 421262022178582819079251857125275655811075621258715892000982433792, (267904833920988021755713804525256419760378275403162741501392437432767 6741632171344981154708908740937465018914268843861959959166259824640, (344732998585264137278518183990826817681052934281348312892269837964114 2787678220408058127307830627732903130370080, (279046200598226503025195411999556640561360813741428047435649929638887 53919896548177368107317435753348858030491248876033001444230813450240, (308870957825708469714089919616978942471477644937229563165812001499328 43558801421871693155057757365937721311264, (656771183507056771530189311265967581848842023836838155327575923027336 7231417358594709909675782579312803883500927862552389383882752, (799951954396033959301943714852765024015676508282446847398265322484737 3923188608000707249878114713577990542482597304562406653952, (23466363972826628201392499018846555677122307675763716232101471027527 31385510173511080446023535356611600781985607364393606053952, (824589189456299460272232522499712919911948713559841899842769532385981 12855896672933306875158098281404737897156577177854801971511296, (307966722179635840758817499013270716673252306547812170829528532448628 13338936968668000741204699921005642771046392163215840641024, (671864379473768418033629622516676579753429300827211122401615840347304 803469022130956639408311949088787461973896350671606510518272, (128499539598992820351912123229293324765984163573666042925341763346397 200867255555940498344706071443480706504903835121904288530432, (712003509559982421602968330751931565620423368514347115901438869479500 3291009114642413545811575696017619213650304742842199751132184576, (780537041854299422180955640564870748807158438050627610525352465330812 80880045689521584534779150595290007047821488685116114688875780112384, (84571260150626419081248266266782657358644797686276480762551836230331 1263747500022686240375016332204045187826779830506604542430113955840, (737068406434883665450664272822492309636096026307936853419320325384204 6739986666788438169058599730940792766509010872017450641534339776512, (215568957236058328757270012892331817013939468018109250548103982506604 1645504557321206042154974627075545758551810297802813790973067264, (442919351931295153592884284649535799804768603304208107000053665550219 26959946667150639888203119876388826270066001602080833955764199489536, (823839097280461907620286638920806726669356358865836126344174606896767 188533711215686517986655163459178679300685528825856, (263372892334932746977602064790619519320992768890760924624030993030214 20283648752621387104869752537088, (763875910121688864250508208444667111781012283131519186809312536280968 766247793271695105624347938400422067785374987427250688, (682914036491523349444023408643992736206940164028684625854043760847402 1606938044305758327936550985723680517471355541344305708793856, (602577396787420197341876891718840309543953979719480289760726515681434 842909709488170918979813059825945362874723168041726527707767898112, (347918673551373669515217187582448634915052644683842214774401857390286 1619493780418222719086171214737491483582140682005426183602176, (118968810066686599955040696108393709552754846084361471872892200679680 619007798574553095290748928, (795671161024590542185406750254776623283813744813188748269315213330146 65820182292848241686198767302294020199386805887021902837980364800, (791993283007778948282145743858672568728576851736939974674827204534160 1645504557321206042199570673037489134827664658359072475234435072, (782210596702728025154090078360177812742567670038536355351095315625435 26959946667150639794667015087020295287635036918256102614578801672192, (426004897768330243396894066289308407462857551899000025589634663746517 26959946668719915229975186958865623913522869182594394113142956228608, (398368568628985152651490710094105244194374545204049522269510639264300 51422017416288054192752119680646912658243703400479471800713218, (563563890988575566245652393913603597651759690958312206039998270219116 3064991081734565309866510382505213193482415091606355968, (525464830352346682976459601223775219904764050636750316674629088567014 6739986666787659948666756559390592780602373476785304363517243047936, (135513558706463057773066259572665371508964247455261100866881911077471 11417981541647699330878535932496792039632928768, (400100608844131944235138599487108082313451206959990079349829336946236 215679573337205118357336120696157045389097155418105818680695231348736, (627939359249070691809962355077312859779956827305305439060260843059047 3292616052686671074585480327290118922304551176317439256909840384, (609101544270764154186438061220538529142570406006769264465410596734497 26959946667150642787822368340708807154784300795507839989540861263872, (652479175682481292003487147179512158254161340957990062502917841738119 548063113999088614608791425365009522057524805632, (276871809952965379561635690462590116672831143556615477648135559499170 183044516589539354745725175581898032716063982080, (604745481173797027809076390394748598686088811473398911842410798005338 365375409375344102205389154611181237580993658896, (465957550610728563634565551731915228952481858309064143421092313179927 414590015418819491089826219844789138884867682910082541119602704, (488703425926869751072175591084400239373182393927063363976097237406745 47890485652059027488312342568276350895606870134751232, (390120392235291617234383444979638398579337170483373637166452197279698 51422017417784266493969631543157776549449748545181839815344128, (653100791680244527999303425412530505740256299399090672392168205373793 187894304249354206421561231306087136277465780977665, (193262532464346240505953723065267591703248895726262392292664451223698 107839786668602559178668061044998077796563110121582856664971990794240, (107045793911947398136197105188293300699239666683373268395539891241589 1464356132721631751216591668375026639666589728768, (523012293529248077643701888156084275077815953025269036072647383210035 46768052394588898899333326840175411942642467995648, (622157257340377525245646024844470880621191809662103051590357979385054 401734511064747568885490689243860726145947788034771106398208, (316313718202282856322693032620188751154014552879090456430616940216284 1684997470165937864956373518112891047494490282124986733440572325888, (584739191018300307347039255066505921203948794043447580870443268686716 786170212464200984337832024928147296822640855405965606912, (783460519482638997081925507192876069457386478570448084824250091133087 561216629431965009342371163569750782700765623353344, (388114081291408893064038973703219574667554554439776426575952568038973 356811925834945961834403238170058273434107905, (409926396074512569171554146069999496317045410843190221223641176833912 210624583435241978498332249021804732601066711684135124654509522944, (111580650341887778146995012026026650925860443325513704063610271717604 25711204870566233450194337934278985553248450736212014274707456, (544049943500270738871790342149343930450085433867843205576488089535164 103621218491187941046757992587795305759564664520750816821249, (487731884289323500594412232131366798086816624309721524464898466942517 12603243328081783594985398931224671869065811749175618961408, (514337490313840329117544989549543721439299793294549724880811538969016 365375409332725730189698268487220464909350354944, (840436795151657314984517695610620173725667736230343246728369440559566 201698643933206250391156973202602652673610826645504, (78166235150270483621568408887054775150313094818439116837713274271947 5868842515129166047418721549004285598248197947392] \ No newline at end of file diff --git a/writeups/icecrax/asis2019/single_bits.py b/writeups/icecrax/asis2019/single_bits.py new file mode 100755 index 0000000..d74b374 --- /dev/null +++ b/writeups/icecrax/asis2019/single_bits.py @@ -0,0 +1,48 @@ +#!/usr/bin/env python + +import random +from Crypto.Util.number import * +from flag import flag + +def gen_rand(nbit, l): + R = [] + while True: + r = random.randint(0, nbit-1) + if r not in R: + R.append(r) + if len(R) == l: + break + R.sort() + rbit = '1' + for i in range(l-1): + rbit += (R[i+1] - R[i] - 1) * '0' + '1' + rbit += (nbit - R[-1] - 1) * '0' + return int(rbit, 2) + +def genkey(p, l): + n = len(bin(p)[2:]) + f, skey = gen_rand(n, l), gen_rand(n, l) + pkey = f * inverse(skey, p) % p + return (p, pkey), skey + +def encrypt(msg, pkey): + p, g = pkey + msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:]) + for b in bin(msg)[2:]: + s, t = gen_rand(n, l), gen_rand(n, l) + c = (s * g + t) % p + if b == '0': + enc.append((c, t)) + else: + enc.append((p-c, t)) + return enc + +p = 862718293348820473429344482784628181556388621521298319395315527974911 +l = 5 + +pkey, skey = genkey(p, l) +enc = encrypt(flag, pkey) +H = pkey[1] ** 2 % p + +print('H =', H) +print('enc =', enc) \ No newline at end of file diff --git a/writeups/icecrax/asis2019/tonelli-shanks.py b/writeups/icecrax/asis2019/tonelli-shanks.py new file mode 100644 index 0000000..507968b --- /dev/null +++ b/writeups/icecrax/asis2019/tonelli-shanks.py @@ -0,0 +1,66 @@ +def legendre(a, p): + return pow(a, (p - 1) // 2, p) + +def tonelli(n, p): + assert legendre(n, p) == 1, "not a square (mod p)" + q = p - 1 + s = 0 + while q % 2 == 0: + q //= 2 + s += 1 + if s == 1: + return pow(n, (p + 1) // 4, p) + for z in range(2, p): + if p - 1 == legendre(z, p): + break + c = pow(z, q, p) + r = pow(n, (q + 1) // 2, p) + t = pow(n, q, p) + m = s + t2 = 0 + while (t - 1) % p != 0: + t2 = (t * t) % p + for i in range(1, m): + if (t2 - 1) % p == 0: + break + t2 = (t2 * t2) % p + b = pow(c, 1 << (m - i - 1), p) + r = (r * b) % p + c = (b * b) % p + t = (t * c) % p + m = i + return r + +H = 381704527450191606347421195235742637659723827441243208291869156144963 +factors = [1504073, 20492753, 59833457464970183, 467795120187583723534280000348743236593] # all of them are coprime + +# The Tonelli–Shanks algorithm is used in modular arithmetic to solve for +# r in a congruence of the form r^2 ≡ n (mod p), where p is a prime number. +# Note: it can be applied only if " Euler's criterion" is fullfiled or "Legendre symbol" = 1 +if __name__ == '__main__': + ttest = [(H,factors[0]),(H,factors[1]), (H,factors[2]), (H,factors[3])] + for n, p in ttest: + print("=====================================================") + print("Legendre symbol: ", legendre(n, p)) + r = tonelli(n, p) + assert (r * r - n) % p == 0 + print("n = %d p = %d" % (n, p)) + print("\t roots : %d %d" % (r, p - r)) + + +# Results: +# p0 = 1504073: +# 399666 +# 1104407 + +# p1 = 20492753: +# 7111848 +# 13380905 + +# p2 = 59833457464970183: +# 34240854883018057 +# 25592602581952126 + +# p3 = 467795120187583723534280000348743236593: +# 308269479959806774875048102517512730884 +# 159525640227776948659231897831230505709 \ No newline at end of file diff --git a/writeups/icecrax/asis2019/understanding_duality_of_(c-t).py b/writeups/icecrax/asis2019/understanding_duality_of_(c-t).py new file mode 100644 index 0000000..b0621c4 --- /dev/null +++ b/writeups/icecrax/asis2019/understanding_duality_of_(c-t).py @@ -0,0 +1,48 @@ +import random +from Crypto.Util.number import * + +def gen_rand(nbit, l): + R = [] + while True: + r = random.randint(0, nbit-1) + if r not in R: + R.append(r) + if len(R) == l: + break + R.sort() + rbit = '1' + for i in range(l-1): + rbit += (R[i+1] - R[i] - 1) * '0' + '1' + rbit += (nbit - R[-1] - 1) * '0' + return int(rbit, 2) + +def genkey(p, l): + n = len(bin(p)[2:]) # n = 229 + f, skey = gen_rand(n, l), gen_rand(n, l) + pkey = f * inverse(skey, p) % p # Return the inverse of u mod v. + return (p, pkey), skey + +def encrypt(msg, pkey): + p, g = pkey + msg, enc, n = bytes_to_long(msg), [], len(bin(p)[2:]) + for b in bin(msg)[2:]: + s, t = gen_rand(n, l), gen_rand(n, l) + c = (s * g + t) % p + if b == '0': + enc.append((c, t)) + else: + enc.append((p-c, t)) + return enc + +def sanity(p, l): + pkey, skey = genkey(p, l) + enc = encrypt(long_to_bytes(0b1010100001111), pkey) + p, g = pkey + for check, t in enc: + s = ((check - t) * inverse(g, p)) % p + print(bin(s)) + +p = 862718293348820473429344482784628181556388621521298319395315527974911 +l = 5 + +sanity(p, l) \ No newline at end of file diff --git a/writeups/icecrax/asis2019/why_better_libraries.py b/writeups/icecrax/asis2019/why_better_libraries.py new file mode 100644 index 0000000..c81b2d7 --- /dev/null +++ b/writeups/icecrax/asis2019/why_better_libraries.py @@ -0,0 +1,26 @@ +import random +from Crypto.Util.number import * +p = 2150 +H = 2314 +pkey = 892 # found through find_pkey() pkey^2 ≡ H (mod p) holds +c = 1353 +t = 517 +s = 483 # found through find_s() + +def find_s(): + for k in range(1000): + s = ((c - t) * pkey + p * k) / H + if(s == int(round(s))): + print(s) + +def find_pkey(): + for i in range (1000): + if H % p == i**2 % p: + print(i) + +# Tests: +print((c-t) % p == s * pkey % p) +print((c-t) * inverse(pkey,p) % p == s % p) +print((c-t) * inverse(pkey,p) % p) +print(s % p) +print(math.gcd(pkey, p)) \ No newline at end of file -- 2.43.0