公钥密码体制之RSA

2024-02-26 13:08
文章标签 密码 rsa 公钥 体制

本文主要是介绍公钥密码体制之RSA，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

记一次密码学上课所学的公钥密码体制学习。从一开始的古典密码到流密码再是分组密码，再是现在的公钥密码体制。

产生原因

公钥密码体制的产生主要是因为两个方面的原因：一是由于常规的密钥密码体制的密钥分配问题，另一种是由于对数字签名的需求。

在对称密钥密码体制中，加密、解密使用同样的密钥，有密钥生成函数将种子密钥生成加密密钥然后从特别的通道由发送者和接受者分别保存。加密、解密得时候，采用这种方法的主要问题在于密钥的生成、注入、存储、管理和分发，特别是随着用户的增加，密钥的需求量也是成倍增加。在网络通信的过程中，密钥的分配是有个难以解决的问题。

而所谓的公钥密码体制，是使用不同的加密密钥和解密秘钥。在加解密过程中，用公钥（Pk）即公开密钥加密，用私钥（Sk）即秘密密钥解密。任何用户都可将传送给此用户的信息用公钥加密发送，而该用户唯一保存的私人密钥是保密的，也只有它能将密文复原、解密。

如果是用来数字签名的话，则是用私钥加密，公钥解密。

在这里主要想记录的是当前使用的比较多的公钥密码体制

1.RSA算法
2.椭圆曲线密码体制（ECC）
RSA

RSA的安全性主要是依赖于大整数分解大质数因子。

PS：https://blog.csdn.net/flurry_rain/article/details/77970691（详细请看）
RSA相关的数论知识
  1. 一个大于1的整数p，若除1和起本身之外没有其他正整数因数（约数），称P为素数。
  2. 若整数a和b最大公约数为1，则称a，b互素，记为（gcd（a，b）= 1）。
  3. 设n为正整数，a和b为整数，若a和b被n除后所得余数相同，称a和b模n同余，记为a≡b（mod n）。此式被称为同余式。若n能整除a则同余式表示为a≡0（mod n）。

两个整数模n同余的等价说法有：a和b被n除余数相同。a-b被n整除。a和b在模n的同一个剩余类中。存在整数s使得a=sn+b。

  1. 同余式的一些运算性质，

（1） 若a≡b（mod n），c≡d（mod n）则有ac≡bd（mod n）。特别的有，ka≡kb（mod n），k为任意整数。

（2） 若a≡b（mod n），d是a，b，n的公因数，则(a/d) ≡(b/d)（mod n/d）。特别的有an≡bn（mod n），n为正整数。

（3） 若ka≡kb（mod n），且k与n互素时，有a≡b（mod n）。（同余式消去律）

  1. 设n为正整数 ,则任何一个整数被n除 ,余数必为0,1,2,…,n-1中的某一个,把整数集中被n除余数相同的数分别归为一类,记为[0],[1],[2]…,[n-1],这样就按模是否同余把整数集分成n类,其中每一类都称为模n的一个剩余类。显然,每个整数必属于上述类中的一类,被n除余数不同的数必属于上述的不同类中。若a0,a1,a3…,an-1分别取自上述类的不同类中,称a0,a1,a3…,an-1为模n的一个完全剩余系,该剩余系中的数两两模n不同余。
  2. 含有未知量的同余式称为同余方程。一次同余方程是最简单的一种,其一般形式为ax≡b（mod n）。若a，n的最大公约数d能整除b，则ax≡b（mod n）有解。且恰有d个解。若a，n的最大公约数d不能能整除b，则ax≡b（mod n）无解。例如同余方程7x≡1（mod 5）。7与5最大公约数为1，能被b=1整除，故有一个解。7x≡1（mod 5）≡6≡11≡21（mod5）。由于7与5互素有消去律得x=3。

一般地 解同余方程的步骤为 ①判断解的情况 ②当同余方程的a，b，n有公因数时 ,约去公因数化简方程 ③利用同余的定义和消去律求方程的解。

  1. 费马小定理：设任意整数a和素数p互素[微软中国4] ，则ap-1 ≡1（mod p）。
  2. 欧拉定理：若n,a为正整数，且n,a互质，(a,n) = 1，则a^φ(n) ≡ 1 (mod n)。
  3. 模运算极其性质：

基本理论:

基本概念：给定一个正整数p，任意一个整数n，一定存在等式 n = kp + r ；其中k、r是整数，且 0 ≤ r < p，称呼k为n除以p的商，r为n除以p的余数。对于正整数p和整数a,b，定义如下运算：取模运算：a % p（或a mod p），表示a除以p的余数。模p加法：(a + b) % p ，其结果是a+b算术和除以p的余数，也就是说，(a+b) = kp +r，则(a + b) % p = r。模p减法：(a-b) % p ，其结果是a-b算术差除以p的余数。模p乘法：(a * b) % p，其结果是 a * b算术乘法除以p的余数。

说明：

  1. 同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。
  2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

基本性质:

（1）若p|(a-b)，则a≡b (% p)。例如 11 ≡ 4 (% 7)， 18 ≡ 4(% 7)（2）(a % p)=(b % p)意味a≡b (% p)（3）对称性：a≡b (% p)等价于b≡a (% p)（4）传递性：若a≡b (% p)且b≡c (% p) ，则a≡c (% p)

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：(a + b) % p = (a % p + b % p) % p （1）(a - b) % p = (a % p - b % p) % p （2）(a * b) % p = (a % p * b % p) % p （3）(a^b) % p = ((a % p)^b) % p （4）结合率： ((a+b) % p + c) % p = (a + (b+c) % p) % p （5）((a*b) % p * c)% p = (a * (b*c) % p) % p （6）交换率： (a + b) % p = (b+a) % p （7）(a * b) % p = (b * a) % p （8）分配率： ((a +b)% p * c) % p = ((a * c) % p + (b * c) % p) % p （9）

重要定理

若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；（10）若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；（11）若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)； （12）若a≡b (% p)，则对于任意的c，都有ac≡ bc (%p)； （13）
RSA算法及证明

1. RSA定理证明：

定理：设p，q是不同的素数，n=pq记φ(n)=(p-1)(q-1),如果e，d是与φ(n)互素的两个正整数（e,d<φ(n)),并满足ed≡1(mod φ(n)),则对于每个整数x,都有xed≡x(mod n)。分析：为了证明xed≡x(mod n)，只要证明φ(n)是xed-x的因数即可。又因为n=pq，而p，q都是素数，故只要证明p和q都是xed-x的因数即可，即xed≡x(mod p) （1）xed≡x(mod q) （2）证明：证明式1，若p是x的因数则式1必然成立 
若p不是x的因数，则由ed≡1(mod φ(n))得ed-1=k(p-1)(q-1),k为任意整数。则xed=xk(p-1)(q-1)+1 = x*（xp-1）k(q-1)
根据费马小定理因为x与p互素所以xp-1≡1（mod p） 
所以xed≡x*（1）k(q-1) ≡x（mod p）同理可证xed≡x(mod q)

2.RSA定理与RSA加密算法：

RSA加密算法为： (1) 取两个大素数p,q (保密)； 
(2) 计算 n=p*q(公开)，φ(n)=(p-1)*(q-1) (保密)； 
(3) 随机选取整数e，满足 gcd(e, φ(n))=1 （e与φ(n)互素）(公开)； 
(4) 计算 d 满足 d*e≡1 (mod φ(n)) (保密)； （d为e的逆元，可通过扩展的欧几里得算法进行求解）
(5) ｛e，n｝为公钥，｛d，n｝为私钥，也可以用｛e，d｝表示密钥对 
(6) 加密时c = xe mod n ；解密时 x = cd mod n 
(7) 签名时c = xd mod n ；解密时 x = ce mod n 
问题：为什么xed≡x(mod n) 就能保证(6)和(7)正确？ 
分析：解xed≡x(mod n)同余式方程，该方程可能有n个解，这n个解都在模n的同一个剩余类中，小于n的解只有一个，由于明文小于n，则该解即是明文x。而xed mod n得到的就是小于n的那个解。 
另外，注意密文c并不等于xe而是c≡xe（mod n）。这里有上一段中我们知道要想求出明文x，解同余式方程xed≡x(mod n)可得，这时只要等式左边的数与X同余就能得到正确的明文。由于c≡xe（mod n），所以可得cd≡xed（mod n）,所以cd≡xe（mod n）。

从另一个角度解释为什么RSA加密和解密过程是互逆的：

将问题改为证明：A^e mod n = B^(e*d)mod n-----------1 
即B^(e*d)mod n = B 
其中A为密文，B为明文。 证明：因为ed+1=（p-1）（q-1）所以B^(e*d)=B^(k(p-1)(q-1)+1), 
当B与n互素时，根据欧拉定理有: 
B^(k(p-1)(q-1)+1) mod n 
= B*B^ k(p-1)(q-1) mod n 
= (B mod n )*((B^(p-1)(q-1))^k mod n) 
= (B mod n ) * (((B^(p-1)(q-1)) mod n) ^ k ) mod n) 
= B * (1^k mod n) 
=B
当B与n不互素时，由于n=p*q，B必然能被p或者q整除，假设B=k*p,则B与q互素。再运用费马定理有：
B^(q-1) = 1 mod q， 
则（B^(q-1)）^(p-1)K = 1^(p-1)K mod q = 1 mod q, 
即B^k(p-1)(q-1) mod q =1。 
两边同时乘以B，得到 
B^(k(p-1)(q-1)+1) mod q = B 
也就是B^(e*d)mod n = B
RSA算法举例

公钥体制中,单向函数的构造基于大整数n因数分解的困难 ,因而n的两个因数p与q都应取大素数。为便于理解,我们选取两个较小的素数来说明该体制的实施。

例：给定两个素数p=13，q=17 
（1）为用户A和B设计公钥和私钥。 
（2）用户A将明文x=3 加密。 
（3）用户A将明文x=3 加密并签名后发给B，B解密并验证签名试把加密通信过程详细写出。 
解：（1）计算得n=p*q=221，φ(n)=（p-1）*（q-1）=12*16=192。随机选取与φ(n)=192互素的两个数e1=7和e2=13，并建立同余方程7x≡1（mod 192）13x≡1（mod 192）由于7和192；13和192都互素，7x ≡1 ≡ 193 ≡ 385 mod 192，根据消去律得到x = 55即d1=55，同理得到d2 =133.将密钥｛7，55｝和｛13.133｝交给A和B两个人。将n，e1，e2公开，d1，d2交给A和B各自秘密保管。φ(n)=192由密钥制作者保管。（2）A在公钥簿上查询到B的公钥e2=13，得到加密函数 
E2(x) ≡ x^13 (mod 221),对信息x=3进行加密得到密文y≡ 3^13 (mod 221)因为3^2≡9(mod 221);3^4≡9*9≡81(mod 221);3^8≡81*81≡6561≡152(mod 221)所以，3^13 ≡ 3^(8+4+1) ≡152*81*3 ≡ 29 (mod 221)A将密文29发出给B。B使用自己的私钥133进行解密x = D2（y）≡ y^133 ≡ 29^133(mod 221). 用上述方法计算得29^4 ≡ 81 (mod 221); 29^128 ≡ 35 (mod 221);所以，29^133 ≡ 29^(128+4+1) ≡ 35*81*29 ≡ 3 (mod 221)。B得到明文3。（3）A使用自己的私钥55和解密函数对信息x=3进行签名得y=3^55 mod 221.A在从公钥簿上查询B的公钥为13和B的加密函数，对y进行加密z=y^13 mod 221 = 3^（55*13）mod 221 = 3^153 mod 221.计算得z=211。B得到密文后，先查到A的公钥7，用7解密密文z=211，得到y。在使用自己的私钥对y进行验证得到信息x=3。
常见的RSA攻击方法

共模攻击

PS：https://blog.csdn.net/qq_31481187/article/details/70448108（详细请看）

共模攻击，也称同模攻击，英文原名是 Common Modulus Attack 。 
同模攻击利用的大前提就是，RSA体系在生成密钥的过程中使用了相同的模数n。 
假设COMPANY用所有公钥加密了同一条信息M，也就是 
c1 = m^e1%n 
c2 = m^e2%n 
此时员工A拥有密钥d1他可以通过 
m = c1^d1%n 
解密得到消息m 
同时员工B拥有密钥d2 
他可以通过 
m = c2^d2%n 
解密得到消息m如果，此时有一个攻击者，同时监听了A和B接收到的密文C1,C2，因为模数不变，以及所有公钥都是公开的，那么利用同模攻击，他就可以在不知道d1，d2的情况下解密得到消息m。

贴出破解脚本

#coding=utf-8
import sys;
sys.setrecursionlimit(100000);
def egcd(a, b):if a == 0:return (b, 0, 1)else:g, y, x = egcd(b % a, a)return (g, x - (b // a) * y, y)
def modinv(a, m):g, x, y = egcd(a, m)if g != 1:raise Exception('modular inverse does not exist')else:return x % m
def main():n= ???e1= ???e2= ???c1= ???c2= ???s = egcd(e1, e2)s1 = s[1]s2 = s[2]# 求模反元素if s1<0:s1 = - s1c1 = modinv(c1, n)elif s2<0:s2 = - s2c2 = modinv(c2, n)m = (pow(c1,s1,n)*pow(c2,s2,n))%nprint m
if __name__ == '__main__':main()

还有一些RSA的常见攻击方式，本想着直接写下来，但是又想着要是能在介绍这些攻击方式的理论的同时，放上相应的CTF例题会不会更加容易了解，所以就准备另外开一篇有关RSA攻击方式的博文，谢谢观看！

这篇关于公钥密码体制之RSA的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/748972。

相关文章

【测试】输入正确用户名和密码，点击登录没有响应的可能性原因

【测试】输入正确用户名和密码，点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题： 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定，导致点击后无法触发登录操作。 页面可能存在
阅读更多...
研究人员在RSA大会上演示利用恶意JPEG图片入侵企业内网

研究人员在RSA大会上演示利用恶意JPEG图片入侵企业内网

安全研究人员Marcus Murray在正在旧金山举行的RSA大会上公布了一种利用恶意JPEG图片入侵企业网络内部Windows服务器的新方法。  攻击流程及漏洞分析 最近，安全专家兼渗透测试员Marcus Murray发现了一种利用恶意JPEG图片来攻击Windows服务器的新方法，利用该方法还可以在目标网络中进行特权提升。几天前，在旧金山举行的RSA大会上，该Marcus现场展示了攻击流程，
阅读更多...
随机密码生成器应具备哪些默认功能？

随机密码生成器应具备哪些默认功能？

阅读更多...
超级 密码加密 解密 源码，支持表情，符号，数字，字母，加密

超级 密码加密 解密 源码，支持表情，符号，数字，字母，加密

超级 密码加密 解密 源码，支持表情，符号，数字，字母，加密 可以将表情，动物，水果，表情，手势，猫语，兽语，狗语，爱语，符号，数字，字母，加密和解密 可以将文字、字母、数字、代码、标点符号等内容转换成新的文字形式，通过简单的文字以不同的排列顺序来表达不同的内容 源码截图： https://www.httple.net/152649.html
阅读更多...
mysql导出导入数据和修改登录密码

mysql导出导入数据和修改登录密码

导出表结构： mysqldump -uroot -ppassword -d dbname tablename>db.sql; 导出表数据： mysqldump -t dbname　-uroot -ppassword > db.sql 导出表结构和数据（不加-d）： mysqldump -uroot -ppassword dbname tablename > db.sql;
阅读更多...
Ubuntu 环境下ssh的安装、使用以及免密码登录

Ubuntu 环境下ssh的安装、使用以及免密码登录

以两台机器为例：     A12.12.10.11B12.12.10.13 安装： Ubuntu默认安装了ssh客户端，只需要在被登录的机器上安装ssh服务器即可： $ sudo apt-get install openssh-server     启动ssh服务器： $ sudo /etc/init.d/ssh start 查看是否启动成功： $ ps -ef |grep
阅读更多...
ubuntu 20.04 一直卡在登录界面，即使密码正确也无法登录（失败记录）

ubuntu 20.04 一直卡在登录界面，即使密码正确也无法登录（失败记录）

ubuntu 20.04 一直卡在登录界面，即使密码正确也无法登录 这次是装实体机，一次失败的尝试。。。 名称型号CPUIntel Xeon E5-2673 V3GPURTX 3060 mobile 安装的时候不要选install third-party software for graphics and Wi-fi hardware and additional media
阅读更多...
oracle密码维护

oracle密码维护

查看密码是否可以重复使用 SQL> select PROFILE,RESOURCE_NAME,LIMIT from dba_profiles where profile='DEFAULT' and resource_type ='PASSWORD'; PROFILE                        RESOURCE_NAME                    LIMIT ----
阅读更多...
【网络安全】古典密码体制概述

【网络安全】古典密码体制概述

1. 古典密码体制概述 1.1 定义与历史背景 古典密码体制是指在计算机科学和信息安全技术出现之前的传统加密方法。这些方法主要包括替换和易位两种基本形式。古典密码体制的特点是简单、易用，但安全性不高，容易被破解。在古代，人们使用纸、笔或简单的器械来实现加密和解密操作。 定义：古典密码体制是基于简单数学运算和文字替换的加密方法，包括替代密码和置换密码两大类。历史背景：古典密码的使用可以追溯到古
阅读更多...
vsftpd配置用户和密码让其他客户端连接

vsftpd配置用户和密码让其他客户端连接

一、第一个主机:vsftpd下载及配置 前置准备: #卸载防火墙yum -y remove firewalld#为了不让防火墙有影响，iptables配置也清空iptables -Fvim /etc/selinux/confSELINUX=disabled #主要是把它改为disabled或者permissiveSELINUXTYPE=targeted#重启linux让selin
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2