为什么研究这个

我是🕊大王，本来4.6一比完就想写了，硬鸽到今天。主要也是因为一堆作业考试给应付得手忙脚乱的。

这个是我们校内的CTF中的一个题目名为“babyrsa”，下载下来之后是一个babyrsa.py，于是我试图认真地学一下rsa的知识。在《密码编码学与网络安全》这本书中指出：很多的公钥密码体制的理论都基于数论，如果读者接受本章中给出的结论，那么便不必严格地理解数论的有关知识。然而，要完全理解公钥算法，就需要理解这些数论知识。

然而，我对于数论的认知完全停留在初二那个暑假去学院数竞培训的时间，当时有一位老师专门讲到了数论，我第一次听到“模十同余”这个概念，也第一次接触到所谓的中国剩余定理（在当时我的注意力基本都被解析几何和四点公圆的奇葩题目给吸引住了）

自使疑始释

回到主题，在公钥密码体制中基本由6个部分组成：

明文：这是原始未加密的信息或数据，是加密过程的输入。

加密算法：这是一系列用于将明文转换为密文的规则和步骤。在公钥加密中，这个过程利用了公钥。 公钥：这是一个数字证书，用于加密明文或验证签名，公开可获取。任何人都可以使用公钥来加密信息，但只有持有对应私钥的接收者能够解密。

密文：经过加密算法处理后产生的加密过后的信息或数据，只有拥有相应私钥的人才能解密回明文。

解密算法：这是一系列用于将密文转换回明文的规则和步骤。在公钥加密中，这个过程利用了私钥。

私钥：这是一个数字证书，用于解密收到的信息或进行数字签名，应当被密切保护，不对外公开。私钥确保只有密钥的持有者才能解密那些用对应公钥加密的信息。

1976年，两位美国计算机学家Whitfield Diffie 和 Martin Hellman，提出了一种崭新构思，可以在不直接传递密钥的情况下，完成解密。这被称为"Diffie-Hellman密钥交换算法"。这个算法启发了其他科学家。人们认识到，加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可，这样就避免了直接传递密钥。

这种新的加密模式被称为"非对称加密算法"。如果公钥加密的信息只有私钥解得开，那么只要私钥不泄漏，通信就是安全的。

（1）乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。

（2）甲方获取乙方的公钥，然后用它对信息加密。

（3）乙方得到加密后的信息，用私钥解密。

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。

RSA是一种分组密码，其密文和明文都是0~n-1之间的证书，通常n是1024位的二进制数或309位的十进制数，也就是说n<2^1024。明文分组进行加密，每个分组的二进制值均小于n。

（1）选定两个素数(p,q)（保密的，选定的）

（2）n=pq(公开的，计算得出的)

（3）e,满足gcd(φ(n),e)=1,1<e<φ(n)（公开的，选定的）

（4）d≡e^-1(mod φ(n))（保密的，计算得出的）

私钥为{d，n}，公钥为{e,n}。假设A公布了密钥，用户B要发送消息M给A，那么用户B只需要计算 M≡C^d(mod n)并发送给C；在接收端，用户A计算M≡C^d(mod n)以解出消息M。

需要注意的是，在rsa加密解密中都需要计算某个整数模n的整数次幂，如果先求整数的幂再模n，soleidei，中间的结果会非常大。可以运用模算术的性质解决，去简化为对中间的计算结果模n。因为在rsa中使用的指数很大，所以还得考虑幂运算的效率问题如果正常计算x^16次方，需要进行15次乘法，这样子的话对加密解密的时间就上了很大的压力。但是可以取重复每个部分结果的平方（2^2,2^4,2^8,2^16）,就只需要四次乘法了。

给出普遍的计算a^b mod n的算法，其中里面的变量c不是必须的，整数b表示为二进制数，引入它为了解释算法，c的终值即使指数值：

c←0;f←1
for i←k downto 0
	do c←2*c
	   f←(f*f) mod n
	if bi=1		（bi i是下标）
		then c←c+1
		  f←(f*a) mod n
	return f

我是懂哥，比赛看到这里假装自己懂了，然后开始看题目。后来我发现对于真正的rsa系列题目还有一系列难点涉及到e的取值（3，17，65537），各个情况的互相求解，不同的攻击方式等等，也要了解如中国剩余定理，费马定理，Miller-Rabin算法什么的，暂且按下不表。

Baby的rsa

来看一下源码：

from gmpy2 import lcm
from Crypto.Util.number import getPrime, bytes_to_long

p = getPrime(1024)
q = getPrime(1024)
n = p*q
e = 54666
h = lcm(p - 1 , q - 1)
flag = b'FCTF{***********}'
m = bytes_to_long(flag)
c = pow(m, e, n)
print('n: ', n)
print('h: ', h)
print('c: ', c)




'''
n:  25527104228224088488040470054859297799684430729586201999927539150044992353999083976287914924970569469434686168557247480896928199907052200737794107820101535432772515334456482673511185210116841919416618006696356771202410487435695207310741143088507315599413718818919895412368893805095614918899139207456629111515498628424508456173008212962396577655489900115537922862725514355690650346542020236913649627901430140820374812887483132677589636744805036428604336253688728768629554430310965303561197842773841768036265483485885167914975226451364872214945774294272151759555341126251417977165442601848916571897507614450138696307441
h:  3190888028528011061005058756857412224960553841198275249990942393755624044249885497035989365621321183679335771069655935112116024988381525092224263477512691929096564416807060334188898151264605239927077250837044596400301310929461900913842642886063414449926714852364986926546111725636951864862392400932078638939397162813314446093112008451870874459413340817966632865485406320788272316381137437957674310631802876313435533326327324210320100692584743680300917008843045504725648240011406960704841222641567549521400885041138306803979812904472944466100873729786606242613061006721938847831340052029664934674085291935568007804584
c:  13816656057233504242725466607519098922616296851282996573245636803888321169952138063011430581813327223855035775201965978271601144858474586480811825971179893352623779199435743915535990803704703901640138034283878850535619383284762202523145531803148037944606221169858890092284283768859214489478888725916054874525393017572123038563581085488781982829726844109883458439559508856073477596828594786184067989967020470472291721891068880110540699901476565507918536144452248311628215837448639176024403880919704090284307989085868140402906218076204485172179740170107661474514833980476371750724966421481356221210695767530318458804012

看起来非常吓人。

在这个位数的情况下，我不知道能不能把他分解，使用一些常规手段得等上好久，觉得可能没那么简单。

注意到，e = 54666，并不是一个素数。目前我们只知道e，h，c，n。我刚开始以为可以直接从h和n直接逆推出p和q，还是太天真了。然后去网络上找，发现有人讲过这种题型，但是讲的都有点奇怪，我当时没懂，又自己开始琢磨。在探索过程中，我发现一个名曰“欧几里得算法”的东西可能有所帮助，于是我去看了一下wiki，发现就是辗转相除法其实。

def gcd(a, b):
    while b != 0:
        t = a % b
        a = b
        b = t
    return a

想必这个迭代，各位都有印象，它广泛地出现在编程题目中。当然也有：

def gcd(a, b):
    return a if b == 0 else gcd(b, a % b)

扩展欧几里得算法是用于计算两个整数a和b的最大公约数以及满足贝祖等式ax+by=gcd(a,b)的整数解x和y的一种算法。

评价是有点汗流浃背了，我开局第一题做的这一题（一见钟情），到晚上都没想好是什么个思路。翻阅资料，了解到大素数和大整数的位数是尤为重要的，可以有奇淫巧技来破解。观察到n和h的位数相近，继续学习并尝试使用下列代码。

h = 
e = 
c = 
n = 

print(len(bin(h)[2:]))
print(len(bin(n)[2:]))

#bin(h)将变量 h 转换为二进制字符串表示；[2:]切片操作，从第三个字符（二进制数的起始字符）开始截取到末尾，去掉了前面的 '0b'，这是二进制数前缀；len()：获取字符串的长度，即二进制数的位数。

输出2045和2048。

n是两个大素数p和q的乘积。而h是p-1和q-1的最小公倍数。因此，它们的位数可以用来估计p和q的位数。具体地说，如果n是一个 2048 位的数字，那么p和q通常会是1024位的素数。

进行穷（ti）举（shen）攻击，进行遍历，差三位所以选择（4，8）。这应该算是…穷举吧，试着当作φ的倍数去解，然后使用扩展欧几里得解密钥。其中，模逆是指对于给定的两个整数a和n，如果存在一个整数b，使得 ab≡1(mod n)，那么b就是a在模n意义下的乘法逆元，通常记作a−1。当然，≡表示模同余关系

复习一下上面的解密，其中M≡C^d(mod n)，d就是指数e的模φ的模逆，(e*d)%φ(n)=1 。需要指出的是，加密操作是指数运算，解密操作则是对密文进行模幂运算，其结果是明文的平方。因此，解密后的结果 m_2 是明文的平方。

最终代码如下：

import gmpy2
from Crypto.Util.number import *
h =
e =
c =
n =

#print(len(bin(h)[2:]))
#print(len(bin(n)[2:]))

for gcd_val in range(4, 8):
    phi = h * gcd_val
    try:
        d = gmpy2.invert(e // 2, phi)
        m_2 = pow(c, int(d), n)
        flag = long_to_bytes(gmpy2.isqrt(m_2))
        print(flag)
    except ZeroDivisionError:
        continue

可以得出 b’FCTF{***********}’（真实值是一串字符），提交即可。

这种题型算是比较基础的题目，当然让我学到很多，感觉很有意思。

一语点醒撒比人

（4.21更新，绷不住了有点）

但是，经“客服4.5 9:00-12：00”点拨，我霍然觉得自己就是个傻子。

他指出：e并不是一个素数，可以执行：

print(((p-1)*(q-1))/h)

可以得出为2。一般来说，对于任意两个数a,b，有LCM(a,b)×GCD(a,b)=a×b。由于p和q是素数，GCD(p−1,q−1)GCD(p−1,q−1)很可能是1。h=LCM(p−1,q−1)≈(p−1)×(q−1)，当你用LCM（p-1，q-1）除以（p-1）*（q-1）时，你本质上是在用它自己，或者用一个非常接近它自己的数字来除以它。结果应该接近1。在（p-1）和（q-1）中存在一个小的公因子，会使得LCM略小于h。比如这里输出为2意味着 (p-1) 和 (q-1) 共有一个因子，导致它们的最小公倍数恰好是乘积的一半。那么，上述的代码就显得非常的傻，我们完全可以利用如下代码得出结论：

import gmpy2
from Crypto.Util.number import long_to_bytes

h =
e =
c =
n =
gcd_val = 2
phi = h * gcd_val
d = gmpy2.invert(e // 2, phi) 
m_2 = pow(c, int(d), n)
flag = long_to_bytes(gmpy2.isqrt(m_2))
print(flag.decode('utf-8'))

太难绷了babyrsa，真的是一题宝宝题啊。

于是回到博客的开篇句：

“吾魂兮无求乎永生，竭尽兮人事之所能” ——Pindar

DONE.

参考文章(Sir,this way.)