鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 网站安全 > 加密解密 > >

仿射密码(古典)[转]

来源:互联网 作者:佚名 时间:2015-10-09 06:15
仿射 密码 简介 : 仿射 密码 和移位 密码 一样, 也是一种替换 密码 . 不同的是, 移位 密码 中, 我们使用的是模n加; 而在下面的仿射 密码 中, 我们使用的上一节中介绍的模n乘. 在安全性方面, 仿射 密码 同移位 密码 一样, 都是极其差的, 不仅因为他们的原理简

 仿射密码简介:
   仿射密码和移位密码一样, 也是一种替换密码. 不同的是, 移位密码中,
我们使用的是模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

网友评论
<