由二次剩余想到的一个简单的加密算法

wsc810

该加解密的算法要求事先双方约定好密钥k及大整数N=p*q.即N是两个大素数的乘积，其中密钥满足如下同余关系式， k^2=1 (mod N).设明文为m,加密过程如下 m*k=c (mod N) 解密为 c*k=m (mod N). 这种方法很简单吧！实用时可选取的N应稍大一点

mathematica

很简单，不过一点都不安全！N=p*q，那么由数论的知识知道有四个x满足 x^2=1 mod(N) 由c*k=m (mod N) 得到(c*k)^2=c^2*k^2=c^2=m^2 (mod N) 所以知道了c（当然也知道N-c），也就差不多知道了m（m的值只有四种情况，不过已经知道了两种了，一个是c，另一个是N-c）。 看来你肯定不是搞密码的。

mathematica

要想搞出一套加密算法，不是很容易的事情，不是专业人士就不要去碰了。 Rabin加密算法 http://blog.sina.com.cn/s/blog_64370f500100lhqz.html

mathematica

很显然，上面的算法比你的安全！

好地方

...所以知道了c（当然也知道N-c），也就差不多知道了m... mathematica 发表于 2011-3-2 20:46

要是真这么容易从c得到m，那么分解N岂不轻而易举？

wsc810

2# mathematica Mathematica.一楼上没说清楚，实际上真正需要保密的是N，k则可由N的两个因子，p,q算出，公式如下， (p+q)/(p-q)=k (mod p) 在这种情况下，是否安全呢？欢迎讨论 补充内容 (2014-3-1 09:54): (p+q)/(p-q)=k (mod N)

mathematica

要是真这么容易从c得到m，那么分解N岂不轻而易举？ 好地方 发表于 2011-3-2 22:20

我是说他的加密不安全,m的值只有四个,却已经知道了两个,这种加密算法没多大价值

wsc810

7# mathematica 问题是这种对称的加密算法，另外两个值（即明文），不是轻易就可以算出的，相当于求 X^2=c^2 (mod N).这种方法等同于大数分解，若N不公开，破解几乎不可能

好地方

8# wsc810 这个算法显然不能抵抗已知明文攻击，因此必须经常更换密钥，最好是一次一密，但这样运作成本就高了。

wsc810

mathematica 发表于 2011-3-3 10:59
我是说他的加密不安全,m的值只有四个,却已经知道了两个,这种加密算法没多大价值

怎么不安全了，没明白你的意思，给你个例子
PowerModList[1, 1/2, 91]={1, 27, 64, 90}