RSA加密算法

加密步骤如下图所示

1、选择一堆不相等且足够大的质数 p 和 q

2、计算 p 和 q 的乘积 n = p * q

3、计算 n 的欧拉函数 ϕ(n)=(p-1)*(q-1)

欧拉函数 ϕ(n)：统计 小于n 的所有和 n 互指的数的个数。

注意：这里说的互质的数包括1

例如：ϕ(6)=2，小于 6 的数有 [1,2,3,4,5] ，和 6 有公因数的数有 [2,3,4]，和 6 互质的数有 [1,5] ，所以 ϕ(6)=2

质数的欧拉函数为质数本身减一

例如：ϕ(7)=6，小于 7 的数有 [1,2,3,4,5,6] ，这些数都和 7 互质，所以 ϕ(7)=6

因为 p 和 q 均为质数，所以 ϕ(n)= ϕ( p ) * ϕ ( q ) = ( p - 1 ) * ( q - 1 )

4、选一个与 ϕ(n) 互质的整数 e ( 1 < e < ϕ(n) ,e通常取 65537 )

5、计算出 e 对于 ϕ(n) 的模反元素 d ( d*e mod ϕ(n) = 1 )

模反元素（逆元）的计算需要通过扩展欧几里得算法实现，最后算出的 d 为 e 的系数

# 通过python函数实现扩展欧几里得算法，
# 结果返回为(最大公因数,x,y) , 
# a*x + b*y = gcd(a,b) , 
# gcd(a,b)为 a 和 b 的最大公因数
def extended_gcd1(a,b):    # 扩展欧几里得算法，通过循环实现
    old_s=t=1
    old_t=s=0
    old_r=a
    r=b
    while r!=0:
        q=old_r//r
        old_s,s=s,old_s-s*q
        old_t,t=t,old_t-t*q
        old_r,r=r,old_r%r
    return (old_r,old_s,old_t)

6、加解密

明文为 m

密文为 c

加密算法 ( e , n )

计算方法： m^e mod n = c （ m的e次方 模 n 得到密文c ）

加密算法需要知道 e 和 n

e 通常取的是一个素数，最常见的就是 65537
n 就是素数的乘积（通常取两个素数 p、q，也会有取多个素数的情况），而取的素数一般都很大，512 bit 、1024 bit 、2048bit 、4096bit 等（这里的 bit 就是指二进制数的位数，比如 512 bit 指 512 位2进制数 ）

# python 代码表示为
c = m ** e % n

解密算法 ( d , n )

计算方法： c^d mod n = m （c 的 d 次方模 n 得到明文 m）

解密算法需要知道 d 和 n， 要求出 d 就需要知道素数 p 和 q，通过欧拉函数计算出 ϕ(n)=(p-1)*(q-1) ，再通过扩展欧几里得算法求出 e 的系数 d

d 就是e关于n的逆元
n 这里取两个素数的乘积

# python 代码表示为
m = c ** d % n 

以上就是RSA加解密的过程及其原理
我当时学习是看B站博主 可厉害的土豆 的视频学的，不想看文字的可以看看视频

---

加密：已知 m=3194 , 选 p=976643 , q=565583 , e=65537，求密文 c

解：先根据已知条件p，q求出 n ，再通过明文模 n 最后得到密文 c

n = p * q = 976643 * 565583 = 552372677869

c = m ** e % n = 3194 ** 65537 % 552372677869 = 348234702383

---

解密：已知 c=348234702383 ，p=976643 , q=565583 ，e=65537,求明文m

解：现根据已知条件 p 和 q 求出 n 和 ϕ(n) ，再通过 e 和 ϕ(n) 求出 d，最后通过 d 和 n 求出明文 m

n = p * q = 976643 * 565583 = 552372677869

ϕ(n)=(p-1)*(q-1) = 976642 * 565582 = 552371135644

通过扩展欧几里得算法求出 e 的系数 d = 211173212133

m = c ** d % n = 348234702383 ** 211173212133 % 552372677869 = 3194

---

以上就是加密和解密的过程了。
下面给两个个CTF中的RSA基础密码题

---

源地址：https://buuoj.cn/challenges#RSA

打开压缩包后得到一个 txt 文件，文件内容如下：

在一次RSA密钥对生成中，假设 p=473398607161 ， q=4511491 ， e=17
求解出d作为flga提交

已知 p 、q 、e，要我们求 d ，直接跑 python 脚本

def extended_gcd1(a,b):    # 扩展欧几里得算法，根据RSA密码原理计算 e 的系数 d
    old_s=t=1
    old_t=s=0
    old_r=a
    r=b
    while r!=0:
        q=old_r//r
        old_s,s=s,old_s-s*q
        old_t,t=t,old_t-t*q
        old_r,r=r,old_r%r
    return (old_r,old_s,old_t)
# d * e + phi_n * x = 1
p=473398607161
q=4511491
e=17
phi_n=(p-1)*(q-1)
d= extended_gcd1(e, phi_n)[1]
print(d)
# 运行结果：125631357777427553

跑出来了直接用 flag{} 包起来

flag{125631357777427553}

---

源地址：https://buuoj.cn/challenges#rsarsa

打开压缩包后有一个 txt 文件，内容如下：

Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.

p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
e = 65537
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034

Use RSA to find the secret message

已知 p、q、e、c ，我们通过 phi_n 求出 d ，通过 d 和 n ( n = p * q ) 来解出明文 m 。不多说了，直接跑脚本。

def extended_gcd1(a,b):
    old_s=t=1
    old_t=s=0
    old_r=a
    r=b
    while r!=0:
        q=old_r//r
        old_s,s=s,old_s-s*q
        old_t,t=t,old_t-t*q
        old_r,r=r,old_r%r
    return (old_r,old_s,old_t)
p =  9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
q =  11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
n=p*q
e =  65537
c =  83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
phi_n=(p-1)*(q-1)
# 通过扩展欧几里得算法求出 e的系数 d
d= extended_gcd1(e, phi_n)[1]
# m = c ** d % n 
m=pow(c,d,n)
print(m)
# 运行结果：5577446633554466577768879988

老样子，flag{}包起来直接交

flag{5577446633554466577768879988}

以上均为个人理解，如果内容有误或没讲清楚的地方请指正，谢谢