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

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}