univariate_coppersmith_method
#0ctf2021finals from Crypto.Util.number import * from secret import flag from os import urandom def gen(n_size, m_size): alpha = 0.5 delta = 0.03 d_size = int(delta * n_size) k_size = int((alpha + delta - 0.5) * n_size) c_size = int(n_size…
#RSA #quadratic_residue （mon でのquadratic residue） #univariate_coppersmith_method #Suspicious_Prime https://furutsuki.hatenablog.com/entry/2020/06/01/023111#crypto-Omni-Crypto LSB と MSBがあわせて1024bitくらいわかるので解ける
#CONFidenceCTF2019Teaser #RSA https://ctftime.org/task/7836 You can't break my public key if you don't know it, amirite? The flag format is: p4{letters_digits_and_special_characters}. def bytes_to_long(data): return int(data.encode("hex"),…
#rtactf from Crypto.Util.number import getPrime, isPrime, inverse import os if __name__ == '__main__': # Plaintext (FLAG) m = int.from_bytes(os.getenv("FLAG", "FAKE{sample_flag}").encode(), 'big') # Generate key p = getPrime(600) q = getPr…
#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) …
#rarctf2021 from random import getrandbits from Crypto.Util.number import getPrime, long_to_bytes, bytes_to_long def keygen(): # normal rsa key generation primes = [] e = 3 for _ in range(2): while True: p = getPrime(1024) if (p - 1) % 3: …
#midnightsun2021finals sage: q = 1 ....: while not q.is_prime(): ....: q = 2*random_prime(2**511, proof=False) + 1 ....: ....: def smooth(b, B): ....: n = 1 ....: while log(n)/log(2) < b: ....: n *= random_prime(B, proof=False) ....: retur…
#SECCON_Beginners_2022 from Crypto.Util.number import * from flag import flag p, q, r = getPrime(512), getPrime(256), getPrime(256) n = p * q * r phi = (p - 1) * (q - 1) * (r - 1) e = 2003 d = inverse(e, phi) flag = bytes_to_long(flag.enco…
#!/usr/bin/env sage from Crypto.Util.number import bytes_to_long as b2l def generate(): p = random_prime(2 ** 1024) q = random_prime(2 ** 1024) e = random_prime(200, False, 150) d = inverse_mod(e, (p-1)*(q-1)) n = p * q return [n, e, p, q,…
RSAで同一modにおける2つの暗号文があり、2つの平文の差が小さい時に使える攻撃。つまり このとき、としてresultantでを消去した を求めるとはだけの式になり、univariate coppersmith methodで小さい根を求められれば、Franklin-Reiter Related Message Att…
#angstromCTF2019 https://ctftime.org/task/8342 RSA and univariate coppersmith method https://furutsuki.hatenablog.com/entry/2019/04/25/143959#Crypto-130ptsWALL-E
from Crypto.Util.number import bytes_to_long flag = "LAYER7{CENSORED}" p = random_prime(2^512) q = random_prime(2^512) N = p * p * q e = 0x10001 piN = p * (p-1) * (q-1) d = inverse_mod(e, piN) m = bytes_to_long(flag) ct = pow(m, e, N) asse…
#asisctffinals2021 #!/usr/bin/env python3 from Crypto.Util.number import * from flag import flag def genparam(nbit): while True: a, b = getRandomRange(2, nbit), getRandomRange(32, nbit) if (a ** b).bit_length() == nbit: return a ** b def g…
#n1ctf2021 from Crypto.Util.number import * from secret import flag p = getPrime(512) q = getPrime(512) n = p*q x = 2021*p+1120*q h = (inverse(x,n)+x)%n e = 65537 c = pow(bytes_to_long(flag), e, n) print('n =', n) print('c =', c) print('h …
RSAで同一のを暗号化したがあるとき（すなわち個の暗号文と剰余の法が得られるとき）、CRTで上の暗号文を構成するととなるため乗根を求めると解ける、という問題 generalized hastads broadcast attack とすると、はそれぞれでを根に持つ ここでで、でとなる…
#corctf2021 from Crypto.Util.number import bytes_to_long n = 7354261656064787756554403678873802520293938142515873772154439835685178740118351616322183701392955956899384404680418797770537628910806512688360356290494174865360783635826735966404…
#rtactf import os # Plaintext (FLAG) plaintext = os.getenv("FLAG", "FAKE{sample_flag}").encode() plai = plaintext[:len(plaintext)//2] ntext = plaintext[len(plaintext)//2:] m1 = int.from_bytes(plai + os.urandom(128), 'big') m2 = int.from_by…
univariate coppersmith method multivariate coppersmith 多項式の上の小さい根または上の小さい根を多項式時間で求めるアルゴリズム。つまり または となるようなを求めるということ。Sagemathではsmall_roots というメソッドが生えている。 というパラメ…
