>> 欢迎您,客人登录 按这里注册 忘记密码 在线 搜索 论坛风格  帮助  插件   


>>> 数学分析,奇异积分,几何,代数,微分方程,群与环,数论
Elinkage数学论坛基础数学 [返回] → 浏览:[原创]RSA公钥密码体制的原理和大素数的快速判断 标记论坛所有内容为已读 

 目前论坛总在线 11 人,本主题共有 1 人浏览。其中注册用户 0 人,访客 1 人。  [关闭详细列表]
发表一个新主题 回复贴子 开启一个新投票 ◆此帖被阅读 158 次◆  浏览上一篇主题  刷新本主题  树形显示贴子 浏览下一篇主题
 * 贴子主题: [原创]RSA公钥密码体制的原理和大素数的快速判断 不分页显示此帖  保存该页为文件  本贴有问题,发送短消息报告给版主  加入个人收藏&关注本贴  显示可打印的版本  把本贴打包邮递  把本贴加入收藏夹  发送本页面给朋友   
 ysr 




等级: 新手上路
信息: 该用户目前不在线
威望: 0 积分: 0
现金: 3424 雷傲元
存款: 没开户
贷款: 没贷款
来自: 保密 blank
发帖: 52
精华: 0
资料:  
在线: 15 时 19 分 54 秒
注册: 2013/04/04 00:24am
造访: 2020/07/16 11:53pm
消息 查看 搜索 好友 引用 回复贴子回复 只看我 [楼 主]
  RSA密码体制的原理和大素数的快速判断D)@taHl9
文/王彦会=`!5s<D9b
©Elinkage数学论坛 -- Elinkage极酷超级论坛  6%?7!RP
原理和公式:IJ"
公式:C=M^e MOD n,M=C^d MOD n,ed=1  MOD φ(n)@S>0
其中n为公开模数,C为密文,M为明文,e为私钥,d为公钥。z&Ik!"24vWgf
RSA密码体制加解密的演示:lbs#?k#z$
若n=pq,且p丶q均为素数,则φ(n)=(p-1)(q-1),由于6958000001674999998647为两个11位的素数的积,则可以当公开模数,做密码,这个位数少容易分解,63cQn/
不安全,只是演示RSA密码的原理。_VP/c>V-
则φ(n)=(p-1)(q-1)=6958000001505999998640,选公钥,VcqCL2q=
公钥的选择在1~φ(n)之间,公钥必须与φ(n)互质!F)~`U+[
根据互质数的性质:5wqwb
(1):小数与大质数互质,GyFocPE)
(2):小质数与不含有它的倍数的大合数互质,/QD+/
由于122333221和6958000001505999998640 最大公约数为:1,所以122333221可以做公钥,而122333221模6958000001505999998640 的逆元p|Ue=y(9M
4415860875509221693741,这个逆元就是私钥,私钥比公钥长,演示加密:明文123456789^122333221 MOD 6958000001674999998647=2920527367305698772708, 解密是这样:密文2920527367305698772708^4415860875509221693741 MOD 6958000001674999998647=123456789,还原回去了,这就是过程。3R$X
6958000001674999998647=71000000041*97999999967为两个11位的素数的积,则可以当公开模数,做密码,这个位数少容易分解,不安全,只是演示RSA密码的原理J]q}d1^
©Elinkage数学论坛 -- Elinkage极酷超级论坛  f%g@C'
©Elinkage数学论坛 -- Elinkage极酷超级论坛  b0W{D<(
原理的证明分三段:欧拉定理的证明,其推论的证明,RSA加解密过程的证明。下面是欧拉定理的证明:1!hkCXr`r=
欧拉定理:a^φ(n)=1(modn)j{p%}twM}
证明:C;suB
将1~n中与n互质的数按顺序排布:x1,x2……xφ(n) (显然,共有φ(n)个数)KuA4-1DKls
©Elinkage数学论坛 -- Elinkage极酷超级论坛  E|;"fx'
我们考虑这么一些数:^ei*pM:Q
©Elinkage数学论坛 -- Elinkage极酷超级论坛  cG9L*VG
m1=a*x1;m2=a*x2;m3=a*x3……mφ(n)=a*xφ(n)Or=_U
数m1,m2,m3……mφ(n)(如果将其次序重新排列)必须相应地同余于x1,x2,x3……xφ(n).+CZ
故得出:m1*m2*m3……mφ(n)≡x1*x2*x3……xφ(n) (mod n)^Y
或者说a^[φ(n)]*(x1*x2*x3……xφ(n))≡x1*x2*x3……xφ(n)(mod n)oEG%
或者为了方便:K{a^[φ(n)]-1}≡0 ( mod n ) 这里K=x1*x2*x3……xφ(n)。_z) B8G
可知K{a^[φ(n)]-1}被n整除。但K中的因子x1,x2……都与n互质,所以K与n互质。那么a^[φ(n)]-1必须能被n整除,即a^[φ(n)]-1≡0 (mod n),即a^[φ(n)]≡1 (mod n),得证。 C#8}<5
©Elinkage数学论坛 -- Elinkage极酷超级论坛  RO%+s
当n为素数时就得到费马小定理:dUQWk*rv
费马小定理:对于质数p,任意整数a,均满足:a^p≡a(mod p)8~d'gyVG
©Elinkage数学论坛 -- Elinkage极酷超级论坛  \)A
而RSA密码的加解密过程不同于费马小定理。 9XyE
©Elinkage数学论坛 -- Elinkage极酷超级论坛  GPF"2;,( m
欧拉定理的推论:c?!6NKx
©Elinkage数学论坛 -- Elinkage极酷超级论坛  kI9P0
  若正整数a,n互质,那么对于任意正整数b,有a^b≡a^(b mod φ(n))(mod n)s-T1RV.
©Elinkage数学论坛 -- Elinkage极酷超级论坛  %g3u:WN_QIzm
证明如下:(类似费马小定理的证明)2`?z[<B#
©Elinkage数学论坛 -- Elinkage极酷超级论坛  \uq :W`Vc
  把目标式做一简单变形:a^(b - b mod φ(n))* a^(b mod φ(n))≡ a^(b mod φ(n))(mod n),所以接下来只需要证明a^(b - b mod φ(n))≡ 1 (mod n),又因为:LYlsK
©Elinkage数学论坛 -- Elinkage极酷超级论坛  ?mr
( b - b mod φ(n))| φ(n),不妨设:( b - b mod φ(n))= q*φ(n)(q为自然数),则有a^(q*φ(n))== (a^q)^φ(n),因为a,n互质,那么(a^q)与n也互质,@>n{
©Elinkage数学论坛 -- Elinkage极酷超级论坛  mr7S[.s8
那么就转换到了欧拉定理:(a^q)^φ(n)≡ 1 (mod n),成立。所以我们这个推论成立。2]|/o:@\
©Elinkage数学论坛 -- Elinkage极酷超级论坛  hu%fR$
b mod φ(n)是求模就是求余数的关系不是乘法,不等于b*φ(n),所以解释一下这一步:设b=q∗φ(n)+r,其中0≤r<φ(n),即r=b mod φ(n).于是:4NV
( b - b mod φ(n))| φ(n),nwd
所以前面的成立。S+l/.pYf
©Elinkage数学论坛 -- Elinkage极酷超级论坛  .k&p%!}
©Elinkage数学论坛 -- Elinkage极酷超级论坛  `'p
RSA公钥密码解密过程的证明:wY4|c7F
也就是证明下面的式子:c^d=m(mod n).T'L;
因为根据加密规则:m^e=c(mod n).t`im
于是c可以写成:c=m^e-kn。G|>;
将c代入要我们证明的解密规则:jw#+WZ
(m^e-kn)^d=m(mod n)。#,1
它等同于求证:m^(ed)=m(mod n)。\4lC6M+_OV
这个容易证明:eWzXG'
等式m^(ed)=m(mod n)可以用欧拉定理的推论简单证明的,证明如下:aM!
证明:根据欧拉定理的推论,?)>LiKi_-
若正整数a,n互质,那么对于任意正整数b,有a^b≡a^(b mod φ(n))(mod n)。,AF7vvy
令b=ed,则m^(ed)=m^b,由于ed=1(mod  φ(n)),所以m^(b mod φ(n))=m (mod n)。Lw}
证毕! :{TU|$
当n为素数时照样成立,此时φ(n)=n-1.=[i-iGB[
所以,不同于费马小定理的,我们采用n为素数,当 φ(n)不等于n-1时,还原不回去明文m,就可以确定n为合数。 4&=U
©Elinkage数学论坛 -- Elinkage极酷超级论坛  xWL
RSA公钥密码体制是上世纪70年代~80年代好像是,由3个数学家弄出来的,RSA分别是3位数学家的名字的开首字母。OLer^axf
这个原理就是前面证明过程中的衡等式:m^(ed)=m(mod n)。8dU!/7qh%
数学家居然把它拆开成两个等式,两个过程,没有反例,不会出错。tQ$>PvY8
©Elinkage数学论坛 -- Elinkage极酷超级论坛  N[2
比较这两个公式:a^p≡a(mod p)(费马小定理),m^(ed)=m(mod n)(欧拉原理)(其中ed=1(mod  φ(n)),n为素数也成立)LInYP@g@H=e
显然二者不同,不能同日而语。 `5^<SrGU
©Elinkage数学论坛 -- Elinkage极酷超级论坛  ZN HhKI
当n为素数时原理仍然成立,但此时n不用分解了,不安全了,但我们改变了其功能,不再是加密程序,而是用来判断n是否为素数。明文要 xW_:!R
小位数要短,因为我们要判断的整数n是做除数的,除数比明文短余数就更短,还原不回去明文了,原理失效,如明文用123,4U?%K<a.
则对5位以上的都有效,成立,低于5位的可以用常规法判断。我已经据此原理编成程序,X.`{e8i(|
但不会大整数的快速乘法除法,因此,速度很慢,寻求合作,希望感兴趣会大整数快速乘法除法程序的与我们联系!i|wGA`
我有某整数内的最大素数的估算公式,二者结合就可得到需要的任意大的素数。(公式暂时不发))-gv
欢迎合作,电话:15032042211[Db|z]qEJo{


发贴时间2020/05/08 11:04am IP: 已设置保密[本文共4410字节]  
 ysr 




等级: 新手上路
信息: 该用户目前不在线
威望: 0 积分: 0
现金: 3424 雷傲元
存款: 没开户
贷款: 没贷款
来自: 保密 blank
发帖: 52
精华: 0
资料:  
在线: 15 时 19 分 54 秒
注册: 2013/04/04 00:24am
造访: 2020/07/16 11:53pm
消息 查看 搜索 好友 引用 回复贴子回复 只看我 [第 2 楼]
  有人怀疑是否存在确定性的快速的大素数的判定程序和方法,这就是一个,咋没人看?欢迎讨论,欢迎浏览和沟通!,[+%


发贴时间2020/05/22 10:54pm IP: 已设置保密[本文共126字节]  

 该主题只有一页

快速回复主题: [原创]RSA公钥密码体制的原理和大素数的快速判断
您目前的身份是: 客人 ,要使用其他用户身份,请输入用户名和密码。未注册客人请输入网名,密码留空。
输入用户名和密码: 用户名: 没有注册? 密码: 忘记密码?
上传附件或图片 (最大容量 10000KB)
目前附件:(如不需要某个附件,只需删除内容中的相应 [UploadFile ...] 标签即可) [删除]
选项

使用 LeoBBS 标签?
显示您的签名?
有回复时使用邮件通知您?

使用字体转换?

    快速引用第 楼层的回复
 顶端 加到"个人收藏夹" 主题管理总固顶 取消总固顶 区固顶 取消区固顶 固顶 取消固顶 提升 沉底
加重 取消加重 精华 取消精华 锁定 解锁 删除 删除回复 移动


© 中文版权所有: 雷傲科技
程序版权所有: 雷傲超级论坛  版本: LeoBBS X Build051231
 

本论坛言论纯属发表者个人意见,与 Elinkage数学论坛 立场无关