14

[原创]密码学入门系列(二) 之 仿射密码(古典)

jackozoo 2009-5-19 21:12 17608
【文章标题】: 密码学入门系列(二) 之 仿射密码(古典)
【文章作者】: jackozoo
【作者邮箱】: [email]jackozoo@163.com[/email]
【作者声明】: 只是感兴趣,没有其他目的。失误之处敬请诸位大侠赐教!
--------------------------------------------------------------------------------
【详细过程】
  系列声明: 见(一)
  
  仿射密码简介:
  仿射密码和移位密码一样, 也是一种替换密码. 不同的是, 移位密码中, 我们使用的是模n加; 而在下面的仿射密码中, 我们使用的上一节中介绍的模n乘. 在安全性方面, 仿射密码同移位密码一样, 都是极其差的, 不仅因为他们的原理简单, 更要命的是这两种替换密码没有隐藏明文的字频信息, 这很容易导致破解者轻易的攻破.
  
  
  放射密码中的一些概念:
  
  1) 明密文字母表为Z26
  2) 秘匙 K = (a,b) ∈ Z26_ × Z26 . 其中Z26_ 表示小于26且与26互素(或叫互质)的正整数的集合,这点非常重要的.
  3) 加密变换为 y = (ax + b) mod 26 ;
  
  很简单?(呵呵, 先别急.) 我们先来引入一个定义.
  
  大家知道, 好多东西都有逆, 大家读小学时都知道,两个数相乘乘机为1,则互为倒数, 其实是最简单的逆. 后来, 我们到了高中, 我们学习了逆函数; 到了大学, 我们学习线性代数, 知道两个矩阵的乘积为单位矩阵的话, 则这两个矩阵互为逆矩阵.
  现在我跟大家介绍另一种逆. 叫模逆. 其实很好理解的, 如下:
  若a,b两数的乘积对正整数n取模的结果为1. 则称a,b 互为另外一个的模逆.
  比如:
      3*7 = 21; 21 % 20 = 1 ; 所以3,7 互为 20 的 模逆.
      9*3 = 27; 27 % 26 = 1 ; 所以9,3 互为 26 的 模逆.
  
  如何标记?
  
  若a,b互为n的模逆 , 即b 为a 的模n的逆元 , 则记 b 为 a-1mod n (这里没公式编辑器, a-1中的-1在右上角, 见谅了呵呵).
  
  看了上面的定义, 我们知道:
  只有当 a 与 n 互素的时候, a 才是有模逆的. 其他情况下是不存在模逆的, 比如 2 对26 就没有模逆. 这是个很简单的数学问题, 大家动下手, 画几笔就清楚了.我就不多罗嗦了.
  
  [思考] 大家能快速的求出11对123的模逆吗? (放心,11和123是互素的.)
  
  可能大家会这样想:
  
  设其模逆为 b , 则 必定存在一个整数 t  , 使得等式 11b = 123t + 1 成立.
  
  我们再变化一下, 也即所求为 必须使得 (11b - 1) % 123 = 0 恒成立.
  
  到了这里, 如果使用笔算对b从2开始依次递加穷举的话,将会非常辛苦, 若将123换成一个更大一点的数, 用笔算穷举更是不可能的.
  
  聪明你的肯定想说, 写个程序算就行了啊. 不错, 写个程序帮我们穷举的确很棒, 充分发挥了计算机的作用.
  
  但这里, 我介绍给大家另外一种巧妙的方法 ---- 扩展欧几里德变换:
  
  123 =     1*123+      0*11
  11  =     0*123+      1*11     |11
  2   =     1*123+     (-11)*11  |5
  1   =    (-5)*123+    56*11
  
  
  聪明的你, 一定看出来了吧. 对! 我们将123和11都表示成 x * 123 + y * 11 的 格式, 然后相减, 在最右侧一栏写上每次减去的被减数的倍数. 依次进行, 知道减数变为1为止. 然后我们取第三列的最下面的一个数, 再对123 取模 即得11 对123的模逆.
  对于这个变换, 不清楚的朋友,我劝你们最好动笔画几下. 那样比我在这里说的起作用的多.嘿嘿~~
  
  
  这个算法的好处:
  我们编写这个算法的程序去求任何模逆都是非常高效的, 它帮我们以及CPU都节省了不少时间.
  
  为了加深理解, 来看一个例子:
  
  [例子] :求 1211对13211的模逆 .
  
      13211    1    0          //这一行的1和0是固定的.
      1211     0    1    |10   //这一行0和1也是固定的, 后面的10是13211减掉的1211的倍数.意思为减掉10个1211.
      1101     1    -10  |1    //第一个1为上一行的第二个1抄下来;-10 = 0 - 1*10 (上一行的算这一行的);后面的1依然为减掉的倍数.
      110     -10   11   |10   //-10 为带抄下来, 11 = 1 - (-10) *1 , 10 为倍数.
      1            -120        //很快就到1了, 这时的 -120 就是我们要的.
  
   -120 % 13211= 13091 即为 1211 对13211 的模逆. 怎么样? 不错吧.  呵呵.

  我们可以用如下一段小程序来完成模逆的计算:
  
int Moni(int a,int n)
{
	int p=a,q=n, t;
	int x = 0, y = 1, z = (int)q/p;
	while(1 != p && 1 != q)
	{		
		t = p;
		p = q % p;
		q = t;
		t = y;
		y = x - y*z;
		x = t;
		z = (int) q/p;
	}
	y = y%n;
	if (y<0)
	{
		y += n;
	}
	return y;
}

  
  
  [再来看仿射]
  
  刚才费了这么大的劲, 介绍了模逆, 还是为了在给仿射密码的解密打地基.
  我们看上面的放射密码的加密公式 : y = (ax + b) mod 26 .
  根据简单的数论知识, 我们知道其解密变换为: x = a-1(y-b) mod 26 .(其中a-1中-1在右上角, 为a对26的模逆).
  也即 x = a对26的模逆与(y-b)相乘后的积再对26取模, 最终结果即为解密后的内容.
  
  下面我们来看一个实例:
  
  [例子] 已知仿射密码中密文为JACKOZOO ,字母表为Z26, 秘匙 K = (11,7) , 试解密.
  
  解: 先求11对26的模逆: 11-1mod26 = 19 .
      故解密变换为:  x = 19(y-7) mod 26 ;
      由  JACKOZOO 
      --->  9  0  2  10 14  25  14  14
      --->  12 23 9  5  3   4   3   3
      --->  M  X  J  F  D   E   D   D
  
  所以明文为: MXJFDEDD.
  

  
  好了, 仿射密码的理论介绍就到这里.  附件中为仿射密码学习的小软件. 附带源码. 希望大家用的上. 谢谢 !
  
  
  
--------------------------------------------------------------------------------
【版权声明】: 本文原创于看雪技术论坛, 转载请注明作者并保持文章的完整, 谢谢!

                                                       2009年05月19日 PM 09:11:02
上传的附件:
最新回复 (26)
8
rockinuk 2009-5-19 21:52
2
建議可以再寫多一點~
兩帖有點少~來個5 帖吧~~
14
jackozoo 2009-5-19 22:04
3
整个系列不止5贴, 但是现在一下都写出来, 我没那么多精力啊. 慢慢来吧. 我定期更新.
8
rockinuk 2009-5-19 22:14
4
好了, 仿射密码的理论介绍就到这里. 附件中为仿射密码学习的小软件. 附带源码. 希望大家用的上. 谢谢 !

你自己講介紹到這裏的 <== 不是我講的。
這些內容,我誠收了,當做是「近代密碼學及其應用--軟件加密與解密實作 (看雪學院版)」,的一部分。
其它的內容,等您上繳上來再說。
14
jackozoo 2009-5-19 22:22
5
好的, 十分荣幸!
密码学这方面, 其实我也是一个初学者,  发帖的目的只是分享一下自己的一些理解.
失误之处还请大家多多指正~~
1
lingyu 2009-5-19 22:33
6
支持
相信很多对密码学感兴趣的要这样的文章
8
rockinuk 2009-5-19 22:38
7
放心吧~
有我親自背書,沒問題的。
但內容可不能給我亂寫,這是真的。
我會請 lingyu 大大及其他大大一起“關注”。
你若表現好,我願意推荐你去 MIT 學習。
14
jackozoo 2009-5-19 23:43
8
哈哈, MIT ? 我不是在作梦吧
whzr 2009-5-20 07:46
9
第一次听说“仿射密码”……
关注中 。
30
玩命 2009-5-20 09:58
10
搬个板凳过来学习。。。
8
rockinuk 2009-5-20 14:14
11
對模的逆:

Ex:

1) 11-1 mod 26 = 19,建議寫成 (11)^-1 ,或是 (11^-1)。

2) 逆,可以寫成 逆(inverse element) 。
12
加百力 2009-5-20 14:43
12
一起来温习一下。

看密码学的教材讲过,这里再重复巩固一下。

密码学确实太重要了!
14
jackozoo 2009-5-20 18:19
13
谢谢提醒, 我会注意的.

用M^-1表示M的逆矩阵的确蛮不错的, Thanks.~~
linhanshi 2009-5-23 19:42
14
Support.
ygwh 2009-6-4 21:36
15
谢谢 楼主!
心静 2009-6-14 16:02
16
好好学习!顶!
xtjjcel 2009-6-24 15:05
17
感谢楼主 支持下去
siwen 2009-6-26 14:33
18
感谢LZ,学习了。特别是怎样快速求模逆的方法。
jmuguy 2009-8-25 11:04
19
rockinuk大大好猛啊。。。。推荐去MIT。。。。。梦啊。。。。
14
jackozoo 2009-8-25 20:19
20
那得被推荐的人有实力才行 . 所以猛是取决于双方了. 我们已经没机会了 . 年轻的你们若对密码学感兴趣的, 一定要学好数学. 这样R大才有机会推荐你们的.
jmuguy 2009-8-26 22:33
21
嗯啊。。。好好学习。。。。
wqshandian 2009-8-27 13:01
22
讲得可以,只是我从你的文章中看不到一个反射密码的通用算法,只是简单的作介绍,而说到扩展欧几里德算法时,也只是举了个例子。

个人认为对这些应该作尽详细的描述,必要时需要证明,还有在反射密码分析时需要对分析方法作具体介绍,这样才算完整介绍了反射密码。
redou 2009-8-28 15:51
23
blackhat 2009上好像有人讨论了crack,看了下,E文不好,大意不过倒是理解了,有兴趣的可以看下,应该会有启发
ILHWF 2011-3-19 18:16
24
正用着呢。。。。谢谢楼主了
hbwazxf 2011-3-19 18:27
25
新手学习了。。。。。。。
ghostkming 2012-3-11 20:25
26
2012-3   后生 看看    像是小说  挺有意思
atompure 2012-3-15 18:03
27
Thank you very much
xiaoyezi 2013-1-24 12:58
28
此楼层已删除
返回