gcd(phi, e) != 1のRSA

これを non-coprime exponent RSA って呼ぼうかな

2023-12-03

DiceCTF 2022 | baby-rsa

dicectf2022 non-coprime_exponent_rsa cado-nfs nth-root sage_の素因数分解アルゴリズムにヒントを与える

#diceCTF2022 from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes def getAnnoyingPrime(nbits, e): while True: p = getPrime(nbits) if (p-1) % e**2 == 0: return p nbits = 128 e = 17 p = getAnnoyingPrime(nbits, e) q = getAnno…

2023-11-30

srdnlen CTF 2022 | wtfrsa

srdnlen_ctf_2022 non-coprime_exponent_rsa sage_の素因数分解アルゴリズムにヒントを与える nth-root

#srdnlen_CTF_2022 e: 18959 p: 8853107629856302430942645802685600792214004993921099904332911487775152756152460899671437787731654521568200225685173143721860070387195312109191089843558621 q: 122637763991345814139940390432201063534644731251148…

2023-11-30

RSA

rsaで一部の値がわかっている時 how_to_factorize_n_given_d how_to_recover_cryptographic_keys_from_partial_information rsaのパラメータ同士の関係 rsa-crt phiがわかっているときの素因数分解 non-coprime_exponent_rsa

公開鍵暗号方式の一つ。典型的には以下のようなコードが登場する from Crypto.Util.number import getPrime, isPrime, inverse import os def keygen(): p = getPrime(512) q = getPrime(512) n = p*q e = 65537 d = inverse(e, (p-1)*(q-1)) return (n, e),…

2023-11-28

SECCON Beginners 2021 | p-8 RSA

secconbeginners2021 rsa フェルマー法 gcd(phi,_e)_!=_1のrsa non-coprime_exponent_rsa nth-root

#secconbeginners2021 from Crypto.Util.number import * from random import getrandbits from os import urandom # from flag import flag def gen_primes(bits, e): q = getStrongPrime(bits) p = q while True: p = p-8 # p-8 phi = (p - 1) * (q - 1) i…