RSA加解密算法及题目解析

admin 2023年12月11日11:21:49评论40 views字数 1594阅读5分18秒阅读模式

RSA加解密算法及题目解析  

  一、算法原理

    算法本身基于一个简单的数论知识:给出两个素数,很容易将它们相乘,然而给出它们的乘积,想得到这两个素数就显得尤为困难。如果能够解决大整数(比如几百位的整数)分解的快速方法,那么 RSA 算法将轻易被破解。


RSA加解密算法及题目解析

RSA加解密算法及题目解析

RSA加解密算法及题目解析


1.1 公钥和私钥的生成

RSA加解密算法及题目解析

1.2 RSA 加密

RSA加解密算法及题目解析

1.3 RSA 解密

RSA加解密算法及题目解析

1.4 私钥解密证明

    我们要做的就是证明密文经过私钥的幂取模的结果等于明文,即如下等式成立:

RSA加解密算法及题目解析

证明

RSA加解密算法及题目解析

1)x 和 n 互素


    这种情况,我们主要用欧拉定理就可以证明,证明过程如下:

RSA加解密算法及题目解析

2)x 和 n 不互素

RSA加解密算法及题目解析

RSA加解密算法及题目解析

1.5 安全性证明

RSA加解密算法及题目解析

二、题目解析

2.1 软考网络工程师考试题目

    按照RSA算法,若选取两奇数p=5,q=3,公钥e=7,则私钥d为多少?

A.6    B.7    C.8    D.9

答案解析:

由p=5,q=3,e=7,可知n = p*q =15。φ(n)=(p−1)(q−1)=8

由ed除以φ(n)余数为1得,7d ≡ 1(mod 8),求出d=7,答案为B


2.2 采用python编码,求解出d

RSA加解密算法及题目解析

答案:

#!/usr/bin/python  
#coding:utf-8
#@Author:Mr.Aur0ra

import gmpy2
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
phi = (p-1)*(q-1)#φ(n)在写的时候多用phi代替,因为键盘不好敲出来。

d = gmpy2.invert(e,phi)

#e模phi的逆为d, (e*d)%phi==1 原理上面讲过

print d

或者

#!/usr/bin/python  
#coding:utf-8
#@Author:Mr.Aur0ra

import libnum
p = 3487583947589437589237958723892346254777
q = 8767867843568934765983476584376578389
e = 65537
phi = (p-1)*(q-1)
d = libnum.invmod(e,phi) #e模phi的逆为d,(e*d)%phi==1
print d

    上面的两种解法只是调用的模块不同(gmpy2或libnum),但计算效果是一样的,后面的题目中也会经常使用这些模块,具体想用哪个模块看自己的心情就好。建议使用gmpy2模块,该模块的功能更强大。


    SageMath 是在GPL协议下发布的开源数学软件,并且整合了许多已有的开源软件包到一个基于Python的统一界面下。其目标是创造一个Magma,Maple,Mathematica和Matlab的开源替代品。

    SageMath 包含了从线性代数、微积分,到密码学、数值计算、组合数学、群论、图论、数论等各种初高等数学的计算功能。

    SageMath 的功能十分强大,现在很多CTF比赛的密码学题目都是能用Sage去求解的。建议大家花一部分时间去学习下。


2.3 RSA加解密RSA加解密算法及题目解析

答案:

RSA加解密算法及题目解析


2.4 有如下公式:

 a+b mod n = (a mod n+b mod n) mod n

a-b mod n = (a mod n-b mod n) mod n

a×b mod n = (a mod n×b mod n) mod n

RSA加解密算法及题目解析

试利用上述公式计算15^27(mod 33)的值。

解答:

RSA加解密算法及题目解析

   RSA加解密算法及题目解析

2.5 令p=47,q=71,求用RSA算法加解密的公钥和私钥。已知20*d mod 2000001=1,求d的值。

答案:求d有三种方法:

① 凑数,尝试法
②扩展的欧几里得

RSA加解密算法及题目解析

RSA加解密算法及题目解析




参考文献:

https://zhuanlan.zhihu.com/p/450180396

https://zhuanlan.zhihu.com/p/76006823

https://blog.csdn.net/qq_44775675/article/details/122400841

原文始发于微信公众号(豆豆咨询):RSA加解密算法及题目解析

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2023年12月11日11:21:49
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                   RSA加解密算法及题目解析https://cn-sec.com/archives/2284798.html

发表评论

匿名网友 填写信息