RSA Common Private Exponent Attack
Lattice Based Attack on Common Private Exponent RSA
from Crypto.Util.number import * from random import randint flag = int('SCTF{*******************}'.encode('hex'), 16) d = getPrime(randint(380, 385)) for _ in range(3): p = getPrime(512) q = getPrime(512) n = p * q fn = (p - 1) * (q - 1) e = inverse(d, fn) c = pow(flag, e, n) print 'e'+str(_)+str('=')+hex(e) print 'n'+str(_)+str('=')+hex(n) print 'c'+str(_)+str('=')+hex(c) print '-' * 350
は
くらい
from Crypto.Util.number import * from sage.all import * e0=0x7daf4ce6857ee3627ec3f4a4518d75f4e5ba2bf987d7717920a72671f82f08d7c540412a1899fb7a8a52878819ce188ac75915fa0d7977e27e06263fd092ff600e5563bf3dc12d2e6098b5eb5a303b5daac9724d6eeee12f08baa1b4f0a3159bb6979c7e3abe94e58875b152acbd14acbf7af068593ec24e79766f06015d12f7 n0=0x906d8a1f0061f75b258b41de46e1cfcf51c829821743060aa673e0bd2eb8322b904fd4ce3ddc581d37e403c79753ba71f5e8f697b5f126f8503aad5154942584b5d6de62ec975ce49fd3e3a9c1640e3418b539442f7370cac4b42fcac9f09b493cc8dc9aab2109c28d1015cc8ee62050e992d523e95456b6552a7aae81ee9c47 c0=0x4608aba78dd755f5024f25ff9a29028fa25b5a1c4a2f33adeaed2713e142a188e00a50ffb3652e0aa26e20c1c403978e70572de06ecd2f54d65c6b90e07a3d0a14791bf4c590a70f546c867279fe025def062b6c3741a44ec46b04ef1aeaddd16835d8aa6f490e2c4ebb386f2ffd8607b817151b2077c15dde576477ed2334bc e1=0xb502421310c1e6333c49637c40f0a3987be934eeaf6bbaa2d95db88c6b3df9ab38a719531d1094a36419ad45be5e4a0988301df2657abe223e72a3f821b17662a365f8ab7e7447cbdaceba25e797889409d966e327f975d5ec678d74d14c0c59671cb1962e6c94949f23c57014812dd5ea81e3e9060141425f4fc2d41d0238f n1=0x69b1f909b6b84d33c6aaa1a2872bc24fe8ddfaef60bbb8c61a4dd3ea8fd1f1607143990a20d1a6becbe635ca94a6de1223408a6c4c175ddc2e856578daebad3e593fbd773291b95570a8f11023d0fc9988d8d1d8427405d4e279f697a42b52931fdfdf9c2e4855968ef13b560297ba9b424b0d67becaaf46bb331cbd9e740909 c1=0x4a9e216b42e9ba9af6ee797a4fb5755e6f1078580c9564760c5c03fcc718c2dbe5c281cac0a841188d68dad71792f44fb796af58696c7a154f53da5584636a87e060ff916935343b95885fc7398f418ae5f8c434f90e409e2db52e94544a094ac00547dda6f2ba52354865768b18747941b7aa23bee9d5134864ae15e09134f0 e2=0x73a95e32e7009ea5f3b9ed91d01bf2b867d326c1f04ce22edd0000c74ef02df26feb441a732addfc3521dce6f383d39527982d95940cc71459d6038f83b1323085a8d6b9f2b16b8ad3a8d48e73afd47129a71f95098da2177bfa7d1d7b93af7dfd150add4fa387f01ec05b0281eb2558042043960ca57138749ba5fa838f96a7 n2=0x9059c3add470d2c546e039d51bad153bbcfb04e6e67c30320facfa5aa1ef01db693810548b58f5c750b9795039396a43f6d2bf9335209ba71e3a4655e448d034ffc451034c5adc86ea6ab51c7be7bbd1a8e07b7a448dc0dab58eed134a58260bba42c00d00a377d208eeb6714cbe26252f0eb8ec1b366cbf2f4934654b9dd217 c2=0x28f79a3af282f5049c66aa3d225d38d1f309142a5744f553078500c4709dda23e352a0ef424581494fe84ffc8421ad8671b0868895cc2e28a1dca70afb8b90327dc5d4c5a9009750a254aae75ca41016249051e4415eadf96748bf2f13be6bbb7b938c166d9cc23d2d182835a61f9bf2b4e829f8aa657b72b910e21c60db9dee M = 2**512 A = [ [M, e0, e1, e2], [0, -n0, 0, 0], [0, 0, -n1, 0], [0, 0, 0, -n2], ] A = Matrix(A).LLL() print(A) for row in A: d = abs(row[0]) // M if is_prime(d): m = power_mod(c2, d, n2) print(bytes.fromhex(hex(m)[2:])) break
