RSA练习

2021-10-11 3986 words 8 minutes

Contents

0x00 RSA1

1
2
3
4
5


p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

这道题泄露了dp和dq，分析参考自 https://blog.csdn.net/xiao_han_a/article/details/118516038?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_title~default-1.no_search_link&spm=1001.2101.3001.4242、https://blog.csdn.net/weixin_44110537/article/details/106739798

dp=d%(p-1)
dq=d%(q-1)

m=c<sup>d</sup>+k*n=c<sup>d</sup>+k*p*q 分别同时对q,p取余得
m1=c<sup>d</sup>%p
m2=c<sup>d</sup>%q

m1+k*p=c<sup>d</sup>
m2=(m1+k*p)%q
k*p≡(m1-m2)%q

i为p(mod q)的逆元
k≡i(m1-m2)(mod q)
c<sup>d</sup>=m1+(i(m1-m2)%q )*p
m = c<sup>d</sup> % n= (m1+(i(m1-m2)%q )*p) % n

代码如下：

import gmpy2
n = p*q

I = gmpy2.invert(p, q)                      #I为p(mod q)的逆元，即p*I = 1(mod q)
mp = gmpy2.powmod(c, dp, p)                 #计算mp = c^dp % p
mq = gmpy2.powmod(c, dq, q)                 #计算mq = c^dq % q        

m = (mp + (I * (mq - mp)) * p) % n          #明文求解公式
m = hex(m)[2:]                              #转十六进制数据

flag = ''
for i in range(len(m)//2):
    flag += chr(int(m[i*2:(i+1)*2], 16))

print(flag)

0x01 RSA2

1
2
3
4
5


e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

dp泄露，原理参考 https://blog.csdn.net/weixin_45369385/article/details/109208109?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-4.no_search_link&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromBaidu%7Edefault-4.no_search_link

代码如下：

import gmpy2 

for x in range(1, e):
    if(e*dp%x == 1):
        p = (e*dp-1)//x+1
        if(n%p != 0):
            continue
        q = n//p
        phin = (p-1)*(q-1)
        d = gmpy2.invert(e, phin)
        m = gmpy2.powmod(c, d, n)
        print("flag:",bytes.fromhex(hex(m)[2:]))

0x02 [WUSTCTF2020]babyrsa

c = 28767758880940662779934612526152562406674613203406706867456395986985664083182
n = 73069886771625642807435783661014062604264768481735145873508846925735521695159
e = 65537

n分解为189239861511125143212536989589123569301和386123125371923651191219869811293586459。

代码如下

import gmpy2
from Crypto.Util.number import long_to_bytes

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,n)

print (long_to_bytes(m))

0x03 [GUET-CTF2019]BabyRSA

1
2
3
4
5


p+q : 0x1232fecb92adead91613e7d9ae5e36fe6bb765317d6ed38ad890b4073539a6231a6620584cea5730b5af83a3e80cf30141282c97be4400e33307573af6b25e2ea
(p+1)(q+1) : 0x5248becef1d925d45705a7302700d6a0ffe5877fddf9451a9c1181c4d82365806085fd86fbaab08b6fc66a967b2566d743c626547203b34ea3fdb1bc06dd3bb765fd8b919e3bd2cb15bc175c9498f9d9a0e216c2dde64d81255fa4c05a1ee619fc1fc505285a239e7bc655ec6605d9693078b800ee80931a7a0c84f33c851740
e : 0xe6b1bee47bd63f615c7d0a43c529d219
d : 0x2dde7fbaed477f6d62838d55b0d0964868cf6efb2c282a5f13e6008ce7317a24cb57aec49ef0d738919f47cdcd9677cd52ac2293ec5938aa198f962678b5cd0da344453f521a69b2ac03647cdd8339f4e38cec452d54e60698833d67f9315c02ddaa4c79ebaa902c605d7bda32ce970541b2d9a17d62b52df813b2fb0c5ab1a5
enc_flag : 0x50ae00623211ba6089ddfae21e204ab616f6c9d294e913550af3d66e85d0c0693ed53ed55c46d8cca1d7c2ad44839030df26b70f22a8567171a759b76fe5f07b3c5a6ec89117ed0a36c0950956b9cde880c575737f779143f921d745ac3bb0e379c05d9a3cc6bf0bea8aa91e4d5e752c7eb46b2e023edbc07d24a7c460a34a9a

n = (p+1)*(q+1) - (p+q) - 1，代码如下：

import libnum

n = b-a-1
m = pow(c,d,n)
print(libnum.n2s(m))  #（n2s将数值转化为字符串）

0x04 RSAROLL

题目

RSA roll！roll！roll！
Only number and a-z
（don't use editor
which MS provide）

{920139713,19}

704796792
752211152
274704164
18414022
368270835
483295235
263072905
459788476
483295235
459788476
663551792
475206804
459788476
428313374
475206804
459788476
425392137
704796792
458265677
341524652
483295235
534149509
425392137
428313374
425392137
341524652
458265677
263072905
483295235
828509797
341524652
425392137
475206804
428313374
483295235
475206804
459788476
306220148

{920139713,19} 所代表的是n和e，由此，分解n能得到p、q为18443、49891。参考 https://blog.csdn.net/MikeCoke/article/details/106146568的脚本

import gmpy2
N,p,q,e=920139713,18443,49891,19
d=gmpy2.invert(e,(p-1)*(q-1))
result=[]

with open("data.txt","r") as f:#删掉data.txt的前两行
    for line in f.readlines():
        line=line.strip('\n')#去掉列表中每一个元素的换行符
        result.append(chr(pow(int(line),d,N)))

for i in result:
    print(i,end='')

0x05 [HDCTF2019]basic rsa

import gmpy2
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex

flag = "*****************"

p = 262248800182277040650192055439906580479
q = 262854994239322828547925595487519915551

e = 65533
n = p*q


c = pow(int(b2a_hex(flag),16),e,n)

print c

# 27565231154623519221597938803435789010285480123476977081867877272451638645710

代码如下

import gmpy2
from Crypto.Util.number import long_to_bytes

phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
n = p*q
m = pow(c,d,n)

print (long_to_bytes(m))

0x06 rsa

pub.key如下

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAMAzLFxkrkcYL2wch21CM2kQVFpY9+7+
/AvKr1rzQczdAgMBAAE=
-----END PUBLIC KEY-----

flag.enc

4196 c059 4a5e 000a 96b8 78b6 7cd7 2479
5b13 a8f2 ca54 da06 d0f1 9c28 be68 9b62

参考 https://blog.csdn.net/weixin_30607659/article/details/101533319?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163387389216780274195015%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=163387389216780274195015&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-3-101533319.pc_search_result_cache&utm_term=buu+rsa4&spm=1018.2226.3001.4187

pub.key是公钥，flag.enc是rsa加密后的文件，因此我们只要通过公钥文件解析出n,e,p,q,d，再利用脚本解密rsa加密文件。在 http://tool.chacuo.net/cryptrsakeyparse对公钥进行解析，提取e,n。

然后将n转10进制后，得86934482296048119190666062003494800588905656017203025617216654058378322103517分解p、q得285960468890451637935629440372639283459、304008741604601924494328155975272418463。

代码如下

import gmpy2
import rsa

phin = (q-1)*(p-1)
d = gmpy2.invert(e, phin)

key = rsa.PrivateKey(n, e, int(d), p, q)

with open("flag.enc", "rb+") as f:
    f = f.read()
    print(rsa.decrypt(f, key))

0x07 [NCTF2019]childRSA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


from random import choice
from Crypto.Util.number import isPrime, sieve_base as primes
from flag import flag


def getPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(primes)
        if isPrime(n + 1):
            return n + 1

e = 0x10001
m = int.from_bytes(flag.encode(), 'big')
p, q = [getPrime(2048) for _ in range(2)]
n = p * q
c = pow(m, e, n)

# n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
# c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108

题目给出了n，c，e，但难点在于分解n = p * q，sieve_base是包含了前10000个素数的列表，choice() 方法返回一个列表，元组或字符串的随机项。这里引入费马小定理。参考 https://blog.csdn.net/xiao_han_a/article/details/118670716?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163387505416780366545618%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=163387505416780366545618&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~rank_v31_ecpm-3-118670716.pc_search_result_cache&utm_term=%5BNCTF2019%5DchildRSA&spm=1018.2226.3001.4187

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

拓展可得a^k*(b-1) - 1是b的倍数，而(p-1)和(q-1)由前10000个素数中的若干个素数相乘得到，前10000个素数的乘积记为∏，令∏ = k*(p-1)，由费马小定理，有2^∏-1 = a^k*(p-1)-1是p的倍数，gcd(2^∏-1, n) = p，得到p，但是直接计算2^∏计算量会很大，所以再进一步优化。

2^∏ = 1 (mod p)，即2^∏ = 1 + k₁*p

而2^∏ % n = 2^∏ - k₂n = 2^∏ - k₂pq

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

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

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

代码如下

import gmpy2
import binascii
from Crypto.Util.number import isPrime, sieve_base as primes

#primes为前10000个素数的列表
#计算prd = ∏ primes
prd = 1
for i in primes:
    prd *= i
#p为(2^prd-1)和n的公约数
p = gmpy2.gcd(gmpy2.powmod(2,prd,n)-1,n)
q = n // p
d = gmpy2.invert(e,(p-1)*(q-1))	#计算私钥d
m = gmpy2.powmod(c, d, n)    #解密

flag = binascii.unhexlify(hex(m)[2:])
print(flag)

0x08 RSA4

1
2
3
4
5
6
7
8


N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004 
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114 
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323 
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

三组n和c，联想到中国剩余定理，再仔细观察可以发现n和c的值都没有超过5，它们都是五进制的数，这里需要进行进制的转换。题目没有给出加密指数e，但是根据低加密指数广播攻击的特性猜e=3、10、17等，也可进行遍历。

m<sup>e</sup> = c<sub>1</sub> (mod n<sub>1</sub>)
m<sup>e</sup> = c<sub>2 </sub>(mod n<sub>2</sub>)
m<sup>e</sup> = c<sub>3 </sub>(mod n<sub>3</sub>)

在e=3时，可以得到：
c<sub>x</sub>=m<sup>3</sup> mod n<sub>1</sub>n<sub>2</sub>n<sub>3</sub>
通过对c<sub>x</sub>进行三次开方可以求得明文。

代码如下

import gmpy2
import  binascii

#利用中国剩余定理求解同余方程，aList：余数，mList：模数
def CRT(aList, mList):
    M = 1
    for i in mList:
        M = M * i   #计算M = ∏ mi
    #print(M)
    x = 0
    for i in range(len(mList)):
        Mi = M // mList[i]   #计算Mi
        Mi_inverse = gmpy2.invert(Mi, mList[i]) #计算Mi的逆元
        x += aList[i] * Mi * Mi_inverse #构造x各项
    x = x % M
    return x

if __name__ == "__main__":

    guess = [3,10,17]    
    cList = [int(c1,5), int(c2,5), int(c3,5)]
    nList = [int(n1,5), int(n2,5), int(n3,5)]
    m_e = CRT(cList, nList) #计算m^e
    for e in guess:  #遍历e求解
        m, f = gmpy2.iroot(m_e, e) #m_e开e次根
        print("加密指数e = %d："%e)
        m = hex(m)[2:]
        if len(m)%2 == 1:
            m = m + '0' #binascii.unhexlify()参数长度必须为偶数，因此做一下处理
        flag = binascii.unhexlify(m)
        print(flag)

0x09 [HDCTF2019]bbbbbbrsa

enc如下

1
2
3


p = 177077389675257695042507998165006460849
n = 37421829509887796274897162249367329400988647145613325367337968063341372726061
c = ==gMzYDNzIjMxUTNyIzNzIjMyYTM4MDM0gTMwEjNzgTM2UTN4cjNwIjN2QzM5ADMwIDNyMTO4UzM2cTM5kDN2MTOyUTO5YDM0czM3Mj

能看出c是base64翻转的字符串，使用python的base64.b64decode(str[::-1])得到c的值为2373740699529364991763589324200093466206785561836101840381622237225512234632

encode.py如下

from base64 import b64encode as b32encode
from gmpy2 import invert,gcd,iroot
from Crypto.Util.number import *
from binascii import a2b_hex,b2a_hex
import random

flag = "******************************"

nbit = 128

p = getPrime(nbit)
q = getPrime(nbit)
n = p*q

print p
print n

phi = (p-1)*(q-1)

e = random.randint(50000,70000)

while True:
	if gcd(e,phi) == 1:
		break;
	else:
		e -= 1;

c = pow(int(b2a_hex(flag),16),e,n)

print b32encode(str(c))[::-1]

# 2373740699529364991763589324200093466206785561836101840381622237225512234632

发现竟然直接把c给出了，下面就只需要在50000到70000之间爆破出e的值即可。代码如下

import gmpy2
from Crypto.Util.number import *

q = n//p
phi = (p-1)*(q-1)

for e in range(50000,70000):
	if(gmpy2.gcd(e,phi)==1):
		d = gmpy2.invert(e,phi)
		m = pow(c,d,n)
		if 'flag' in str(long_to_bytes(m)):
			flag = long_to_bytes(m)
print (flag)

0x0A [BJDCTF2020]RSA

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


from Crypto.Util.number import getPrime,bytes_to_long

flag=open("flag","rb").read()

p=getPrime(1024)
q=getPrime(1024)
assert(e<100000)
n=p*q
m=bytes_to_long(flag)
c=pow(m,e,n)
print c,n
print pow(294,e,n)

p=getPrime(1024)
n=p*q
m=bytes_to_long("BJD"*32)
c=pow(m,e,n)
print c,n

'''
output:
12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120  13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
979153370552535153498477459720877329811204688208387543826122582132404214848454954722487086658061408795223805022202997613522014736983452121073860054851302343517756732701026667062765906277626879215457936330799698812755973057557620930172778859116538571207100424990838508255127616637334499680058645411786925302368790414768248611809358160197554369255458675450109457987698749584630551177577492043403656419968285163536823819817573531356497236154342689914525321673807925458651854768512396355389740863270148775362744448115581639629326362342160548500035000156097215446881251055505465713854173913142040976382500435185442521721  12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
'''

由于e小于100000且存在 pow(294,e,n) 的表达式，可以爆破求出其值，两个n值公用了一个q，可以通过gcd函数很快找到q的值。代码如下

import gmpy2
from Crypto.Util.number import *

for e in range(100000):
	res = pow(294,e,n1)
	if (res == output):
		break	
		
p = gmpy2.gcd(n1,n2)
q1 = n1//p
phi1 = (p-1)*(q1-1)
d = gmpy2.invert(e,phi1)
m = pow(c1,d,n1)
flag = long_to_bytes(m)
print(flag)