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

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

* 如果两个正整数，除了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)的整数解

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。

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

题目：

在一次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}

下载拿到的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