RSA算法中密钥对可交换使用的证明

简介:

【前言】RSA算法研究中的一点随笔

RSA算法简述(类C风格描述):
    设P、Q为2个大素数;
    N=P*Q;
    T=(P-1)*(Q-1);
    找到某数E,使其满足E与T互素(E与T的公约数只有1);
    找到某数D,使其满足(E*D) % T == 1;
    则:(D、N)与(E、N)即为可互换的加密(解密)密钥对。

设加密明文为 M, 加密后的密文为C。下面过程假设(E、N)为加密用的公钥,(D、N)为解密用的私钥。
加密:C= (M的E次幂) % N;
解密:M= (C的E次幂) % N;

证明(D、N)与(E、N)即为可互换的加密(解密)密钥对:
如(D、N)与(E、N)可互换,需满足如下2个条件:

1、(D*E) % T == 1;
证明:((E*D) % T ) == ((D*E) % T);

2、需满足D也与T互素

证明:假证D与T不互素,则可描述:
    D==a1*X;(X>1)
    T==a2*X;(X>1)
由(D*E) % T == 1;    
==> (a1*X*E) % (a2*X) ==1;
==> a1*X*E == b*a2*X+1;
==> (a1*E-b*a2)*X==1;
==> X只能==1,且 a1*E-b*a2==1,如X==1,即反证失败。

证明完成










本文转自 张宇 51CTO博客,原文链接:http://blog.51cto.com/zhangyu/663378,如需转载请自行联系原作者
目录
打赏
0
0
0
0
235
分享
相关文章
|
5月前
|
Go 语言中实现 RSA 加解密、签名验证算法
随着互联网的发展,安全需求日益增长。非对称加密算法RSA成为密码学中的重要代表。本文介绍如何使用Go语言和[forgoer/openssl](https://github.com/forgoer/openssl)库简化RSA加解密操作,包括秘钥生成、加解密及签名验证。该库还支持AES、DES等常用算法,安装简便,代码示例清晰易懂。
112 12
|
7月前
|
RSA加密算法详解与Python和Go实现
RSA加密算法详解与Python和Go实现
508 1
|
7月前
|
介绍一下比较与交换算法
【10月更文挑战第20天】介绍一下比较与交换算法
50 0
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
国标非对称加密:RSA算法、非对称特征、js还原、jsencrypt和rsa模块解析
558 1
支付系统,网络安全06----支付安全---,机密性,加密算法,目前最流行的加密算法,AES加密算法,目前最流行的非对称加密算法RSA,对称加密和非对称加密的优缺点,非对称加密是基于非常复杂的数学算法
支付系统,网络安全06----支付安全---,机密性,加密算法,目前最流行的加密算法,AES加密算法,目前最流行的非对称加密算法RSA,对称加密和非对称加密的优缺点,非对称加密是基于非常复杂的数学算法
基于GA遗传算法的悬索桥静载试验车辆最优布载matlab仿真
本程序基于遗传算法(GA)实现悬索桥静载试验车辆最优布载的MATLAB仿真(2022A版)。目标是自动化确定车辆位置,使加载效率ηq满足0.95≤ηq≤1.05且尽量接近1,同时减少车辆数量与布载时间。核心原理通过优化模型平衡最小车辆使用与ηq接近1的目标,并考虑桥梁载荷、车辆间距等约束条件。测试结果展示布载方案的有效性,适用于悬索桥承载能力评估及性能检测场景。
基于双向RRT算法的三维空间最优路线规划matlab仿真
本程序基于双向RRT算法实现三维空间最优路径规划,适用于机器人在复杂环境中的路径寻找问题。通过MATLAB 2022A测试运行,结果展示完整且无水印。算法从起点和终点同时构建两棵随机树,利用随机采样、最近节点查找、扩展等步骤,使两棵树相遇以形成路径,显著提高搜索效率。相比单向RRT,双向RRT在高维或障碍物密集场景中表现更优,为机器人技术提供了有效解决方案。
基于和声搜索优化算法的机器工作调度matlab仿真,输出甘特图
本程序基于和声搜索优化算法(Harmony Search, HS),实现机器工作调度的MATLAB仿真,输出甘特图展示调度结果。算法通过模拟音乐家即兴演奏寻找最佳和声的过程,优化任务在不同机器上的执行顺序,以最小化完成时间和最大化资源利用率为目标。程序适用于MATLAB 2022A版本,运行后无水印。核心参数包括和声记忆大小(HMS)等,适应度函数用于建模优化目标。附带完整代码与运行结果展示。
基于GA遗传优化的最优阈值计算认知异构网络(CHN)能量检测算法matlab仿真
本内容介绍了一种基于GA遗传优化的阈值计算方法在认知异构网络(CHN)中的应用。通过Matlab2022a实现算法,完整代码含中文注释与操作视频。能量检测算法用于感知主用户信号,其性能依赖检测阈值。传统固定阈值方法易受噪声影响,而GA算法通过模拟生物进化,在复杂环境中自动优化阈值,提高频谱感知准确性,增强CHN的通信效率与资源利用率。预览效果无水印,核心程序部分展示,适合研究频谱感知与优化算法的学者参考。
基于AES的遥感图像加密算法matlab仿真
本程序基于MATLAB 2022a实现,采用AES算法对遥感图像进行加密与解密。主要步骤包括:将彩色图像灰度化并重置大小为256×256像素,通过AES的字节替换、行移位、列混合及轮密钥加等操作完成加密,随后进行解密并验证图像质量(如PSNR值)。实验结果展示了原图、加密图和解密图,分析了图像直方图、相关性及熵的变化,确保加密安全性与解密后图像质量。该方法适用于保护遥感图像中的敏感信息,在军事、环境监测等领域具有重要应用价值。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等