crt
#ECDH #InvalidCurveAttack #CRT 楕円曲線の位数がある程度小さい数を含むように素因数分解できる場合に、楕円曲線のgenerator * (order / factor)をやると、位数がfactorな部分群のgeneratorが求まる(位数を調整するテク)。あとは #CRT で復元 #!/usr/bin…
#CRT
離散対数問題に対するアプローチの一つ。 DLPでもECDLPでも同じアルゴリズムが適用できる。 DLPに対するPohlig-Hellman Attack 前提として、巡回群 の位数 が次のように素因数分解可能であるとする。よくあるのは素数 を法とする乗法群で、その位数はなので…
#FireshellCTF2019 E, C, N が与えられているRSAの問題 パラメータが長くて収まりきらなかったのでgistに貼った https://gist.github.com/theoldmoon0602/b901a875f8a53b1ecdbcfbaeb9bf3d48 Nがあまりに大きすぎるので明らかに怪しい。とりあえずfactordb.co…
中国人剰余定理 CRT
#HITCON_CTF_2022 from random import SystemRandom from Crypto.Cipher import AES from hashlib import sha256 from secret import flag rand = SystemRandom() def polyeval(poly, x): return sum([a * x**i for i, a in enumerate(poly)]) DEGREE = 128 …
#cyber_apocalypse_ctf_2021 from Crypto.Util.number import getPrime, bytes_to_long from random import randint FLAG = b'CHTB{??????????????????????????????????}' flag = bytes_to_long(FLAG) def keygen(): p, q = getPrime(1024), getPrime(1024) …
EllipticCurve option 1では との結果を得ることができる。ただし時折 が壊れた値になるらしい option 2では 任意の平文 に対してを計算してもらえる まずは楕円曲線上の点を集めて楕円曲線のパラメータを当てるところからやる。 に対して 同様に この2式に…
https://furutsuki.hatenablog.com/entry/2020/07/20/142730#crypto-coelacanth_vault CRT
#wanictf2021spring from Crypto.Util.number import bytes_to_long with open("flag.txt", "rb") as f: flag = f.read() flag = bytes_to_long(flag) assert flag <= 10 ** 103 upper_bound = 300 while True: try: mod = int(input("Mod > ")) if mod > up…
RSAで同一のを暗号化したがあるとき(すなわち個の暗号文と剰余の法が得られるとき)、CRTで上の暗号文を構成するととなるため乗根を求めると解ける、という問題 generalized hastads broadcast attack とすると、はそれぞれでを根に持つ ここでで、でとなる…
#CRT
#googlectf2021 // Copyright 2021 Google LLC // // Licensed under the Apache License, Version 2.0 (the "License"); // you may not use this file except in compliance with the License. // You may obtain a copy of the License at // // http://w…
#HITCON_CTF_2022 from Crypto.Util.number import bytes_to_long as b2l from Crypto.Util.number import long_to_bytes as l2b import random Zx.<x> = ZZ[] def convolution(f, g): return (f * g) % (x ^ n-1) def balancedmod(f, q): g = list(((f[i] + q/</x>…
#SECCON_CTF_2022_Quals #kurenaif from Crypto.Util.number import * from Crypto.Random import * from flag import flag p = getPrime(512) q = getPrime(512) r = getPrime(512) n = p * q * r e = 2 * 65537 assert n.bit_length() // 8 - len(flag) > …