从RSA原理到CTF题解的学习之路

2021-03-19 5,231

0x01 序言

RSA算法是一种非对称的加密算法,通常是先生成一对RSA密钥,其中之一是保密密钥(私钥),由用户保存;另一个为公开密钥(公钥)可对外公开;要加密传输内容时,比如A要给B传输信息,此时A先用B的公钥将内容加密后传输,B收到A传输过来的信息后用自己的私钥解密。

ctf的密码学除了常见的编码以及古典密码学之外,最难的考点基本上就是RSA了,那么从"Bob and Alice's story about RSA"开始吧!!!


0x02 数论

* 如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。
* 欧拉函数:定义:任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?),计算这个值的方法就叫做欧拉函数,以φ(n)表示。
* 对于素数p, φ(p)=p-1,对于对两个素数p,q, φ(pq)=pq-1,欧拉函数是积性函数,但不是完全积性函数.
* 对于一个正整数N的素数幂分解N=P1^q1*P2^q2*...*Pn^qn,则φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).
* 除了N=2,φ(N)都是偶数.
* 如果n可以分解成两个互质的整数之积,n = p1 × p2,则φ(n) = φ(p1p2) = φ(p1)φ(p2)
* 扩展欧几里得算法是欧几里得算法(又叫辗转相除法)的扩展。除了计算a、b两个整数的最大公约数,此算法还能找到整数x、y(其中一个很可能是负数)。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)。有两个数a,b,对它们进行辗转相除法,可得它们的最大公约数——这是众所周知的。然后,收集辗转相除法中产生的式子,倒回去,可以得到ax+by=gcd(a,b)的整数解

0x03 Processes


1.Alice选择了61和53  (在常见的RSA加解密中这两个数字一般特别大,目前能被破解的这个两个数)

>n=61*53=3233


n值的长度为密钥长度,用二进制表示的长度为12位,所以密钥长度为12位,一般在利用中RSA密钥长度为1024位,重要长度为2048位。


2.计算欧拉函数

>φ(n) = (p-1)(q-1)

即φ(3233)=3120


3.选择随机数e,1< e < φ(n),且e与φ(n) 互质


随机选择e=17,一般e值越大越安全


4.计算模反元素d

ed ≡ 1 (mod φ(n))->ed - 1 = kφ(n)->17x + 3120y = 1->(x,y)=(2753,-15)

即d=2753


所以根据上述的过程,可以看出Bob的公钥为(3233,17),Alice的私钥为(3233,2753)


密钥生成的过程中出现的字母有

p
q
n
φ(n)
e
d

只有公钥是公开的其余不公开,但是一般的n值特别大所以不用担心p和q能被分解,在知道公钥(n,e)的条件下,求解d的步骤如下


ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。
φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。
n=pq。只有将n因数分解,才能算出p和q。

 0x04 加密与解密


Bob拿公钥(3233,17)对密文m做加密处理,设m=65,则加密

m^e=c (mod n)

使用python语法的加密算法

c=pow(m,e,n)

Bob发送给Alice的内容c就是2790


Alice拿到加密后的c为2790之后,使用私钥进行解密

c^d ≡ m (mod n)

使用python语法的解密算法

m=pow(c,d,n)

Alice解密之后得到的密文m就是65


0x05 RSA的入门例子

题目:

在一次RSA密钥对生成中,假设p=473398607161,q=4511491,e=17

求解出d作为flag提交


直接根绝rsa加解密算法求d

from gmpy2 import *
p=473398607161
q=4511491
e=17
phi=(p-1)*(q-1)
d=invert(e,phi)
print d

#flag{125631357777427553}


0x06 BJD2020RSA

下载拿到的zip中存放的是加密步骤以及加密算法内容如下

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


直接看加密过程就知道总共输出了五个数字,output中也刚刚好就是五个输出依次为c, n ,pow(294,e,n), c ,n

这五个数已经给过了那么可以直接进行解密,位置不知道的就是“e”,根据RSA加密步骤我们可以知道加密的过程必须使用e,且e的范围在1<e<getprime(n)之间的,但是加密的代码已经告诉使用的e的范围为1<e<100000,那么可以直接给出的信息调用求出e即可

output=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
n=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
for e in range(100000):
    res=pow(294,e,n)
    if(res==output):
        print e

得到e=52361

看加密算法可以看到两个n公用的是q,那么可以照两个n值的公约数,即q=gcd(n1,n2)

得到q=99855353761764939308265951492116976798674681282941462516956577712943717850048051273358745095906207085170915794187749954588685850452162165059831749303473106541930948723000882713453679904525655327168665295207423257922666721077747911860159181041422993030618385436504858943615630219459262419715816361781062898911


然后按照加密算法逆推得到m

n1=p*q则p=n1/q

from gmpy2 import *
from Crypto.Util.number import *
n1=13508774104460209743306714034546704137247627344981133461801953479736017021401725818808462898375994767375627749494839671944543822403059978073813122441407612530658168942987820256786583006947001711749230193542370570950705530167921702835627122401475251039000775017381633900222474727396823708695063136246115652622259769634591309421761269548260984426148824641285010730983215377509255011298737827621611158032976420011662547854515610597955628898073569684158225678333474543920326532893446849808112837476684390030976472053905069855522297850688026960701186543428139843783907624317274796926248829543413464754127208843070331063037
n2=12806210903061368369054309575159360374022344774547459345216907128193957592938071815865954073287532545947370671838372144806539753829484356064919357285623305209600680570975224639214396805124350862772159272362778768036844634760917612708721787320159318432456050806227784435091161119982613987303255995543165395426658059462110056431392517548717447898084915167661172362984251201688639469652283452307712821398857016487590794996544468826705600332208535201443322267298747117528882985955375246424812616478327182399461709978893464093245135530135430007842223389360212803439850867615121148050034887767584693608776323252233254261047
output=381631268825806469518166370387352035475775677163615730759454343913563615970881967332407709901235637718936184198930226303761876517101208677107311006065728014220477966000620964056616058676999878976943319063836649085085377577273214792371548775204594097887078898598463892440141577974544939268247818937936607013100808169758675042264568547764031628431414727922168580998494695800403043312406643527637667466318473669542326169218665366423043579003388486634167642663495896607282155808331902351188500197960905672207046579647052764579411814305689137519860880916467272056778641442758940135016400808740387144508156358067955215018
c1=12641635617803746150332232646354596292707861480200207537199141183624438303757120570096741248020236666965755798009656547738616399025300123043766255518596149348930444599820675230046423373053051631932557230849083426859490183732303751744004874183062594856870318614289991675980063548316499486908923209627563871554875612702079100567018698992935818206109087568166097392314105717555482926141030505639571708876213167112187962584484065321545727594135175369233925922507794999607323536976824183162923385005669930403448853465141405846835919842908469787547341752365471892495204307644586161393228776042015534147913888338316244169120
for e in range(100000):
    res=pow(294,e,n1)
        if(res==output):
        print e
        break
q=gcd(n1,n2)
print q
p=n1/q
phi=(p-1)*(q-1)
d=invert(e,phi)
m=pow(c1, d, n1)
flag=long_to_bytes(m)
print flag

拿到flag


本文作者:Am1azi3ng

本文为安全脉搏专栏作者发布,转载请注明:https://www.secpulse.com/archives/155156.html

Tags:
评论  (0)
快来写下你的想法吧!

Am1azi3ng

文章数:8 积分: 130

没有说明吖

安全问答社区

安全问答社区

脉搏官方公众号

脉搏公众号