RSA 运算方法?

hc2

有人知道　RSA（Rivest-Shamir-Adelman)　的运算方法吗？

还有
这个怎样来的？

Fermat's Theorm
===========
a^p mod p = a

and

a*x mod p =1

结果
inverse of A
x=a^(p-2) mod p


其实mod 有酱的算法呢？可以　加减　　　或　　　乘除吗？
可以“搬”来“搬”去吗？

微中子

RSA的我不懂,
fermats theorem没有时间想,不过书上应该有的.
哪为数论高手帮忙解答^^

至于Mod呢.

我只能说加减成都能够.

比如(以下的不是证明)

=代表三条横线的

17 = 2 (mod 5)
17 + 4 = 2 + 4 (mod 5)
21 = 1 (mod 5)

17 - 3 = 2 -3 (mod 5)
14 = -1 (mod 5)
14 = 4 (mod 5)

17*2 = 2*2 (mod 5)
34 = 4 (mod 5)

这些都可以.

不过,比如

32 = 2 (mod 6)
32/2 = 16
2/2 = 1
不过
16 不= 1 (mod 6)

所以一般上不能这样除.
要有一些特定的情况才能够成立.

很久没有动这些了.
请高手们指点.

[ Last edited by 微中子 on 7-11-2004 at 08:40 AM ]

RSA加密系统是公开钥匙加密法(PUBLIC-KEY CRYPTOGRAPHY)最漂亮的应用.

何谓公开钥匙加密法?

有别于传统的秘密钥匙加密法,如果BOB要SEND一封加密讯息给ALICE,他就用ALICE的公开钥匙加密(ALICE的公开钥匙是公开给所有人都知道的).ALICE收到BOB的加密讯息后,就用另一把秘密钥匙解密(秘密钥匙只有ALICE知道).简单来说,公开钥匙加密法是用两把不同的钥匙来加密和解密.RSA加密法的出现解决了困扰多时的钥匙发送问题提供了完美的解决方法.

好了,大概明白RSA的一些背景了吧.接下来就看看RSA的实际上是如何操作.

开始,选2个质数P和Q.我用P=17和Q=5来解释.
然后将P*Q,得到另外一个数字,称之为N,所以 17*5=N=85
另外,我们得选一个数字E.E只要不被数字Z=(P-1)(Q-1)整除即可.在这里,我选E=5
好了,数字N和E就是我们的公开钥匙.

如何加密:
假设BOB要SEND一个字母"X"(代表一个吻)给ALICE.他用数字24来代替X.
他作这样的运算,
C=M^E(mod N)
=24^5(mod 85)
=79(mod 85)

79就是密文.BOB将79SEND给ALICE.别人会对这个数字无可奈何,因为要从79作逆向操作得到明文24是件不简单的任务.这是模式算法(mod)的魅力.

如何解密:

ALICE收到密文数字79后,在还没开始解密前,她要用Z和E算出她的秘密钥匙,数字D,才可以解密(上面说了,公开钥匙只可用来加密讯息,并不可用来解密).

数字D必须符合这个特征:E*D恒等于1(mod Z).(要计算D,还要有一个算法,可以简单又快速的计算D)
ALICE计算后,D=13.
她要作这样的计算:
M=C^D(mod N)
=79^13(mod 85)
=24
=X(明文)

所以,ALICE的公开钥匙是(N,E)和秘密钥匙是(N,D).如果要破解BOB SEND给ALICE的密文,必须知道秘密钥匙D,要知道D就必须知道Z,要知道Z就一定要知道组成N得两个质数P和Q.在这个例子的N很容易就被分解成17和5两个质数,进而得知秘密钥匙D.如果N是足够大的话,RSA是破不了的!运用在银行业务上的RSA,N是采取了有305个位数的数字,如果要分解N的话,即使集合全世界的电脑,还得用比宇宙年龄还要长的时间才能破解.

RSA还可以用来加上DIGITAL SIGNATURE来验证讯息来源的可靠性.像上面的例子,ALICE要REPLY BOB的讯息的话,她先用BOB的公开钥匙加密讯息,然后在用自己的秘密钥匙再加密.BOB收到密文后,就用ALICE的公开钥匙来解密,因为用ALICE的秘密钥匙来加密的讯息只有用ALICE的公开钥匙才可以解密.然后再用BOB自己的秘密钥匙解密就可以得到明文了.这样,BOB可以相信这讯息的确是来自ALICE的.

楼主不要以为我是随便用ALICE和BOB两个名字.在密码界上,的确是用这两个名字来说明关于密码的东西的.其实,我对密码很有兴趣,尤其是RSA.谢谢楼主开这帖子,让大家分享关于密码学的一切.我有对RSA进行过研究,有什么疑问的,可以提出来让咱们一起研究.也请各位数学高手指教.

p/s:还有DIFFIE-HELLMAN KEY AGREEMENT PROTOCOL,如果各位有兴趣,我会再发帖讨论.

hc2

其实最近我拿了医科关于电脑安全的科。。又读到关于RSA 这东西..

我比较好奇的是 如何算 D ....
要算 D 的话 那个公式是这样的
D * E = 1 MOD　Z

但最后　ｔｕｔｏｒ　就告诉我们另一个公式

D * E = kZ + 1

他说他也不知道　第二个如何拿到．但是可以正确的算出钥匙Ｄ　但是要用 try and failure 的方式做

k = 1 => (1)Z+1 = D*E 吗?  不是,再做!!
k=2
k=3
k=4

当然 这有很多答案.

不知道右手有什么方式来拿钥匙D呢?

嗯...医科生也要拿电脑安全的科目?奇怪~

钥匙D是要符合 E*D = 1(MOD Z)
(上面的=是三条横的)

在我提到的例子里:

1)用 Z 除于 E 并确定余数,所以: Z=12E+4

2)再用余数除于E,结果: E=(1*4) + 1

得到余数等于1,然后:

3)重写算式(1)&(2),将余数放左边: 4=Z-12E --- (a) 和 1=E-(1*4) --- (b)

4)将(a)代入(b),我们得到: 1=E-(Z-12E)=13E-Z

5)条件达到,即 E*D除于Z必须等于1,所以: 1+64=13E 这样就可得到 1=13E(MOD Z) (这个=也是三条横)

6)答案是: D=13

可以明白吗?

如果给你Z=48998880和E=61,你用TRIAL AND ERROR来算D,就"大锅"了.因为这个D=2409781 呵~

hc2

哈哈不好意识， 一刻写成医科闹了个笑话！！！ paise...:p

flyingfish

hc2网友请参考以下联接:
Fermat's Theorem (其实有一大堆Fermat's Theorem,这只是其中之一):
http://mathworld.wolfram.com/FermatsLittleTheorem.html

mod的各种运算:
http://mathworld.wolfram.com/Congruence.html

RSA的算法/原理: (和右手网友的相似)
http://mathworld.wolfram.com/RSAEncryption.html