CTF RSA 合集
e很小时： import gmpy2 from functools import reduce from Crypto.Util.number import long_to_bytes def CRT(items): N = reduce(lambda x, y: x * y, (i[1] for i in items)) result = 0 for a, n in items: m = N // n d, r, s = gmpy2.gcdext(n, m) if d != 1: raise Exception("Input not pairwise co-prime") result += a * s * m return result % N, N # e, n, c e = 0x3 n=[0x52d483c27cd806550fbe0e37a61af2e7cf5e0efb723dfc81174c918a27627779b21fa3c851e9e94188eaee3d5cd6f752406a43fbecb53e80836ff1e185d3ccd7782ea846c2e91a7b0808986666e0bdadbfb7bdd65670a589a4d2478e9adcafe97c6ee23614bcb2ecc23580f4d2e3cc1ecfec25c50da4bc754dde6c8bfd8d1fc16956c74d8e9196046a01dc9f3024e11461c294f29d7421140732fedacac97b8fe50999117d27943c953f18c4ff4f8c258d839764078d4b6ef6e8591e0ff5563b31a39e6374d0d41c8c46921c25e5904a817ef8e39e5c9b71225a83269693e0b7e3218fc5e5a1e8412ba16e588b3d6ac536dce39fcdfce81eec79979ea6872793] c=[0x10652cdfaa6b63f6d7bd1109da08181e500e5643f5b240a9024bfa84d5f2cac9310562978347bb232d63e7289283871efab83d84ff5a7b64a94a79d34cfbd4ef121723ba1f663e514f83f6f01492b4e13e1bb4296d96ea5a353d3bf2edd2f449c03c4a3e995237985a596908adc741f32365] data = list(zip(c, n)) x, n = CRT(data) m = gmpy2.iroot(gmpy2.mpz(x), e)[0].digits() print(m) print(long_to_bytes(int(m)).decode()) 解形如$x^2(modp)\equiv r$的同余方程 V&N2020 公开赛 easy_RSA from random import randint from gmpy2 import * from Crypto.Util.number import * def getprime(bits): while 1: n = 1 while n.bit_length() < bits: n *= next_prime(randint(1,1000)) if isPrime(n - 1): return n - 1 m = bytes_to_long(b'flag{************************************}') p = getprime(505) q = getPrime(512) r = getPrime(512) assert m < q n = p * q * r e = 0x10001 d = invert(q ** 2, p ** 2) c = pow(m, 2, r) cipher = pow(c, e, n) print(n) print(d) print(cipher) ''' 7941371739956577280160664419383740967516918938781306610817149744988379280561359039016508679365806108722198157199058807892703837558280678711420411242914059658055366348123106473335186505617418956630780649894945233345985279471106888635177256011468979083320605103256178446993230320443790240285158260236926519042413378204298514714890725325831769281505530787739922007367026883959544239568886349070557272869042275528961483412544495589811933856131557221673534170105409 7515987842794170949444517202158067021118454558360145030399453487603693522695746732547224100845570119375977629070702308991221388721952258969752305904378724402002545947182529859604584400048983091861594720299791743887521228492714135449584003054386457751933095902983841246048952155097668245322664318518861440 1618155233923718966393124032999431934705026408748451436388483012584983753140040289666712916510617403356206112730613485227084128314043665913357106301736817062412927135716281544348612150328867226515184078966397180771624148797528036548243343316501503364783092550480439749404301122277056732857399413805293899249313045684662146333448668209567898831091274930053147799756622844119463942087160062353526056879436998061803187343431081504474584816590199768034450005448200 ''' c = pow(m, 2, r) ...