扫二维码下载作业帮
3亿+用户的选择
下载作业帮安装包
扫二维码下载作业帮
3亿+用户的选择
使用RSA算法,已知p=13,q=17,d=7,求e=?
作业帮用户
扫二维码下载作业帮
3亿+用户的选择
f(n)=(p-1)(q-1)=192de=1mod192 e=55(解法如下：令个x,192x+1=7e当x=2时,e=55）
为您推荐：
其他类似问题
扫描下载二维码扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
求联立同余式x+4y≡0(mod143),2x-9y+84≡0(mod143)的解
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
9x+36y≡0(mod143),8x-36y+336≡0(mod143),相加得17x+50≡0(mod143)17x+50=143tx=(143t-50)/17同理可求出yt为参数
为您推荐：
其他类似问题
以下各字母都指整数.1式*9+2式*4得,
17x +84*4 =143m1
(注:与==mod 143等价)集中17的倍数或者说各项对17取余得,
17x1-1*4=7m1, 与上式相较，得 x-x1+20=8m1两集中7的倍数得, 3x1-4=7m2, 取x1=-1, 回代，m1=-3, x=-45, 4y==45==188, y==4...
扫描下载二维码24小时热门版块排行榜&&&&
(小有名气)
在线: 229.3小时
虫号: 1826029
注册: 性别: GG专业: 信息安全
关于RSA密码中取模计算的理解---mod
附件中图上有个mod的计算，为 3533^（-1）mod 11200 = 6597 是如何计算出来的，求指导！！！
IMG_1007_副本_副本.jpg
& 猜你喜欢
已经有3人回复
已经有10人回复
已经有15人回复
已经有12人回复
已经有19人回复
已经有5人回复
已经有10人回复
已经有11人回复
已经有17人回复
已经有9人回复
stupid is as stupid does...
(著名写手)
在线: 308.1小时
虫号: 897149
注册: 专业: 信息安全
很明显，这得用扩展的欧几里得定理啊，不难，lz看看就能明白了
相关版块跳转
SCI期刊点评
中文期刊点评
论文道贺祈福
会议与征稿布告栏
我要订阅楼主
的主题更新
小木虫,学术科研互动社区,为中国学术科研免费提供动力
违规贴举报删除请发送邮件至：
广告投放与宣传请联系 李想 QQ：
QQ：&&邮箱：
Copyright &
MuChong.com, All Rights Reserved. 小木虫 版权所有RSA算法及数学基础
1. 公钥体制数学基础
由于传统密钥体制出现了困难，例如2000个用户保密通信每个人需要保存1999个密钥（两两保密通信需要共（）/2 = 1999000个密钥，每人保管1999个），在密钥管理分配上有困难。另外由于数字签名（身份认证）的需要增加。
公钥体制解决了上述两个问题，即每个人有一对密钥（公钥和私钥），将公钥公开，私钥自己保管，这样每人只要保管好自己的私钥就可以了。通信时使用收信方的公钥进行加密，收信方使用私钥进行解密。在身份认证时，签名者使用私钥签名，验证签名者使用签名者的公钥验签。当然在实际应用时还有其他的问题需要保证，例如抗抵赖，保持信息的完整性等密码学问题。在本文中先不考虑。
有上述公钥体制的任务中我们知道，区别于其他密钥体制算法，公钥算法需要做到的是将加密密钥（公钥）和加密算法公开，破坏者也不能由公钥和密文破译出明文。只有使用解密密钥（私钥）和解密算法才能解出明文。而且保证通过公钥不能推出私钥。
上述内容可以通过所谓的&单向函数&来实现。（传统的密钥体制中加密算法和解密算法是互逆的。）所谓&单向函数&是指加密函数E和解密函数D。但是已知加密函数E推导其逆运算却非常困难（也就是推导私钥的过程）。所以若不知道解密函数（或私钥）不可能解出明文。
单向函数的实现依赖的是大整数因子分解的难度，根据
算数基本定理：任何大于1的整数都可以分解成素数乘积的形式，并且，如果不计分解式中素数的次序，该分解式是唯一的[微软中国1] 。
这个定理在理论上十分漂亮，但是操作起来却非常困难下表列出了现代最快的分解算法在大型计算机上分解一个大数所用的时间。
2. 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。
4. 同余式的一些运算性质，
（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为正整数。[微软中国2]
（3） 若ka&kb（mod n），且k与n互素时，有a&b（mod n）。（同余式消去律）
5. 设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不同余。
6. 含有未知量的同余式称为同余方程。一次同余方程是最简单的一种,其一般形式为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。.[微软中国3] 一般地 解同余方程的步骤为 ①判断解的情况 ②当同余方程的a，b，n有公因数时 ,约去公因数化简方程 ③利用同余的定义和消去律求方程的解。
7. 费马小定理：设任意整数a和素数p互素[微软中国4] ，则ap-1 &1（mod p）。
8. 欧拉定理：若n,a为正整数，且n,a互质，(a,n) = 1，则a^&(n) & 1 (mod n)。
9. 模运算极其性质：
基本概念：
给定一个正整数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）
3. RSA算法及证明：
1. RSA定理证明：
定理：设p，q是不同的素数，n=pq记&(n)=(p-1)(q-1),如果e，d是与&(n)互素[微软中国5] 的两个正整数（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的因数即可[微软中国6] ，即
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）[微软中国7] 同理可证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)) (保密)； (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个解[微软中国8] ，这n个解都在模n的同一个剩余类中，小于n的解只有一个，由于明文小于n[微软中国9] ，则该解即是明文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）。
3. 从另一个角度解释为什么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[微软中国10] 当B与n不互素时，由于n=p*q，B必然能被p或者q整除，假设B=k*p[微软中国11] ,则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
4. 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&(mod 221)[微软中国12]
所以，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。[微软中国13]
分解式中因数的个数是固定的吗？
是，因为素数不能再分了。即使已知一个大数能分成俩个素数的乘积（已知因数个数）其分解仍然很难吗？
同余方程中若a与n互素则方程必有且只有一个解，这也是RSA加解密函数中使用的。
即使两个和数也可以互素例如8和27
为什么e要与&(n)互素？因为只有e和&(n)互素了，同余方程ed&1(mod &(n))才有且仅有一个解。
两个数的最小公倍数=p*q/两个数的最大公约数，若两个数互素（不一定非得全是素数）则两数最大公约数为1，即互素的两个数的最小公倍数就是这两个数的积。而两个数的公倍数都是其最小公倍数的倍数。所以n=pq是p和q的最小公倍数，而只要证明xed-x是p和q的公倍数（即q和p都是xed-x的因数）就可以证明n是xed-x的因数。
前提是xed-x & n???
根据上述同余式的运算性质（2）：
因为xp-1&1（mod p），
所以（xp-1）k(q-1) &1（mod p）
根据同余式的运算性质（1）：
所以x*（xp-1）k(q-1)&x（mod p）
为什么必有解？因为a是b的倍数？因为未知数本身就是模n的剩余类，而模n的剩余类肯定是存在的。
注意明文必须小于n。
参考模运算规则。
与直接求3^13不同
先签名在加密。
阅读(...) 评论()RSA练习题 - 简书
1.假设需要加密的明文信息为m=85，选择：e=7，p=11，q=13，说明使用RSA算法的加密和解密
1.首先求出模数n=p*q=1432.求出(p-1)*(q-1)=1203.e已知，就不用求了4.找出d满足e*d=1 mod (p-1)*(q-1)，这里d=103然后用n和e作为公钥计算出密文c=m^e mod n=123用n和d作为密钥进行解密计算出m=c^d mod n=85
2. 假设需要加密的明文信息为m=14，选择：e=3，p=5，q=11，试说明使用RSA算法的加密和解密过程及结果？
RSA:1.n=p*q=5*11=55,设m=(q-1)*(p-1)=402.求d, ed=1 mod m. 所以d=273.加密：Y=m^e mod n=14^3 mod 55=494.解密：X=Y^d mod n=49^27 mod 55=14=m解密得到了明文m，证明了计算是正确性。说明：1.算d.原理就不讲了，想知道可以看我回答过类似的问题。比如可以使用估值法：3d=k(q-1)(p-1)+1,k=0,1,2...代入求可以整除3的k。此题k=2，很快得到d=27。2.关于mod，49^27mod55很难计算，一定要将49分成若干次方，然后分别mod55来降低难度。当然，还可以使用有mod功能的计算器。
3.RSA算法：p=43，q=59，加密指数e=13，对明文M=134 879 475 204，计算用RSA加密得到的密文。要详细过程！
p=43，q=59，加密指数e=13N = pq = 2537明文M= 134 879 475 204密文= M^e mod N = 248 579
4.已知RSA算法中，素数p=5,q=7,模数n=35,公开密钥e=5,密文c=10，求明文
RSA的算法涉及三个参数，n、e1、e2。其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1)*(q-1)互质；再选择e2，要求(e2*e1)mod((p-1)*(q-1))=1。(n及e1),(n及e2)就是密钥对。RSA加解密的算法完全相同,设A为明文，B为密文，则：A=B^e1 mod n；B=A^e2 mod n；e1和e2可以互换使用，即：A=B^e2 mod n；B=A^e1 mod n；
5.对于RSA算法，设截获e=5，n=35的用户密文C=10，请问明文M是多少？
n=5*7phi(n)=4*6=24d=e^-1 (mod phi(n))=5M=c^d mod n=5
6. 在RSA算法中,选者两个质数P=17 Q=11,加速密钥为E=7,计算密钥D
R=（17-1）*（11-1）R*23/7余1D=23
7.RSA算法中，素数p=7，q=11，加密密钥e=7，计算解密密钥d
N=pq=7*11=77(p-1)(q-1)=6*10=60根据公式d× e ≡ 1 (mod (p-1)(q-1))又e=7,所以 7*d≡ 1 (mod 60)。。即 7d mod 60 = 1。7x43=301。。301除以6刚好余1.所以d=43______________________________________________下面是公式依据：假设Alice想要通过一个不可靠的媒体接收Bob的一条私人讯息。她可以用以下的方式来产生一个公钥和一个私钥：1.随意选择两个大的质数p和q，p不等于q，计算N=pq。2.根据欧拉函数，不大于N且与N互质的整数个数为(p-1)(q-1)3.选择一个整数e与(p-1)(q-1)互质，并且e小于(p-1)(q-1)4.用以下这个公式计算d：d× e ≡ 1 (mod (p-1)(q-1))5.将p和q的记录销毁。e是公钥，d是私钥。d是秘密的，而N是公众都知道的。Alice将她的公钥e传给Bob，而将她的私钥d藏起来。
8.题目：用RSA算法加密时，已经公钥是（e=7,n=20）,私钥是（e=3,n=20），用公钥对消息M=3加密，得到的密文是_____？
你所说的：n=20d=7公钥e=3私钥对M=3进行加密M'=M^d%n (M的d次方，然后除以n取余数)M'=3^7%20=加密后等於7对M'=7进行解密M=M'^e%n=7^3%20=343%20=3解密后又变成3了
总结：&一&基础RSA算法非常简单，概述如下：找两素数p和q取n=p*q取t=(p-1)*(q-1)取任何一个数e,要求满足e实践接下来我们来一个实践，看看实际的操作：找两个素数：p=47q=59这样n=p*q=2773t=(p-1)*(q-1)=2668取e=63，满足eperl -e "foreach $i (1..9999){ print($i),last if $i*63%2668==1 }"847即d＝847最终我们获得关键的n=e=63取消息M=244我们看看加密：c=M**d%n = 244**847%2773用perl的大数计算来算一下：C:\Temp&perl -Mbigint -e "print 244**847%即用d对M加密后获得加密信息c＝465解密：我们可以用e来对加密后的c进行解密，还原M：m=c**e%n=465**63%2773：C:\Temp&perl -Mbigint -e "print 465**63%即用e对c解密后获得m=244 , 该值和原始信息M相等。http://hi.baidu.com/lsgo/blog/item/5fd0da24dfb8.html
RSA算法它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作，也很流行。算法的名字以发明者的名字命名：Ron Rivest, Adi Shamir 和Leonard Adleman。但RSA的安全性一直未能得到理论上的证明。它经历了各种攻击，至今未被完全攻破...
A a (an) [?, e?(?n)] art. 一（个、件……） abandon [?'baend?n] v.抛弃，舍弃，放弃 ability [?'b?l?t?] n. 能力；才能 able ['e?b(?)l] a. 能够；有能力的 abnormal [aeb'n?:m...
MD5的全称是Message-Digest Algorithm 5，在90年代初由MIT的计算机科学实验室和RSA Data Security Inc发明，经MD2、MD3和MD4发展而来。MD5将任意长度的“字节串”变换成一个128bit的大整数，并且它是一个不可逆的字符...
三、RSA scalabilityRSA可扩展性 Obviously a post-quantum RSA public key n will need to be quite large toresist the attacks described in Section ...
关于Quantum Algorithms for Computing Short Discrete Logarithms and Factoring RSA Integers阅读报告 关于《用于计算短离散对数和因式分解RSA整数的量子算法》阅读报告 一、文章主要思想与工作 ...
《子产为政》 整顿田制作丘赋， 不毁乡校铸刑书。 行己也恭事上敬， 养民以惠使下服。 白云山人
或许大家看题目就会有疑问，自驾车为什么是说绿色的？车不是耗油的吗？不是所有的车都叫新能源汽车，它们有的不耗油,耗电有的混合动力，不污染环境。BYD目前有许多新能源车形型：唐系列、秦、元、宋DM。（当然BYD也不只生产新能源汽车，如F5、F6…）我爸这次开的是唐。 今...
今天注册了简书，来到了这个社区，打开界面一看，没点开任何的文章，光看题目，让我有种知乎＋知音的既视感。当然，我知道这样标题党是不对的。 这界面让我觉得很吵闹。 也不是要贬低谁的意思。其实只是想要找个地方记录一下自己的心情，碎碎念，毕竟已经有一年没有动笔了。小说还是那个鬼样子...
最近得了本好书。 前段时间闹书荒闹得厉害，“渴”得整个人都不好了，往书店跑了好几趟也没遇见自己喜欢的、一眼钟情的书。 我坚信，想要读书，是需要缘分的，并非是随手拿了一本就能看下去，而是在看见那本书的时候，就像看见了初恋情人一样，想立马就拥抱他入怀的感觉。 我不喜欢看让我勉强...