费马小定理,费马小定理应用

[NCTF2019]childRSA(费马小定理)

题目

from random import choicefrom Crypto.Util.number import isPrime, sieve_base as primesfrom flag import flagdef getPrime(bits):while True: n = 2 while n.bit_length() < bits: n *= choice(primes)#primes为前10000个素数的列表 if isPrime(n + 1): return n + 1e = 0x10001m = int.from_bytes(flag.encode(), 'big')p, q = [getPrime(2048) for _ in range(2)]n = p * qc = pow(m, e, n)n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

解题思路

已知{n, c, e}，求解明文

这道题的特点是给出了p和q的生成方法，即从前10000个素数中，随机选择若干个相乘，直到乘积+1是个大素数

通过这一点，怎么分解n = p * q呢

这里引入费马小定理

费马小定理

若b为一个素数，则对于任意整数a，有a(b-1) = 1 (mod b)

根据费马小定理，有a(b-1) - 1是b的倍数

拓展一下，又有ak*(b-1) - 1是b的倍数，系数k为正整数

回到题目中来，根据p和q的生成方式，我们知道(p-1)和(q-1)由前10000个素数中的若干个素数相乘得到

因此，前10000个素数的乘积记为∏，则∏肯定为(p-1)和(q-1)的倍数，令∏ = k*(p-1)

由费马小定理，有2∏-1 = ak*(p-1)-1是p的倍数

gcd(2∏-1, n) = p，得到p，但是直接计算2∏计算量会很大，所以再进一步优化

2∏ = 1 (mod p)，即2∏ = 1 + k1*p

而2∏ % n = 2∏ - k2n = 2∏ - k2pq

两边同时% p，有2∏ % n = 2∏ (mod p)

所以同样有2∏ % n = 1 (mod p)

现在只用计算2∏ (mod n)，模幂计算会比直接幂计算快很多

附上代码：

import gmpy2import binasciifrom Crypto.Util.number import isPrime, sieve_base as primese = 0x10001n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108#primes为前10000个素数的列表#计算prd = ∏ primesprd = 1for i in primes: prd *= i#p为(2^prd-1)和n的公约数p = gmpy2.gcd(gmpy2.powmod(2,prd,n)-1,n)q = n // pd = gmpy2.invert(e,(p-1)*(q-1))#计算私钥dm = gmpy2.powmod(c, d, n) #解密flag = binascii.unhexlify(hex(m)[2:])print(flag)

运行结果

b’NCTF{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}’

flag

flag{Th3r3_ar3_1ns3cure_RSA_m0duli_7hat_at_f1rst_gl4nce_appe4r_t0_be_s3cur3}