[原创]密码学入门系列(二) 之仿射密码(古典)-密码应用-看雪-安全社区|安全招聘|kanxue.com

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

发表于: 2009-5-19 21:12 38026

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

jackozoo

2009-5-19 21:12

38026

【文章标题】: 密码学入门系列(二) 之仿射密码(古典)
【文章作者】: 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;
}

登录后可查看完整内容

[注意]传递专业知识、拓宽行业人脉——看雪讲师团队等你加入！

上传的附件：

Affine_bin.rar （19.17kb，129次下载）
Affine_src.rar （5.22kb，156次下载）

收藏・19

免费・9

支持

最新回复 (28) 1 2 ▶
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 2 楼建議可以再寫多一點~ 兩帖有點少~來個5 帖吧~~ 2009-5-19 21:52 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 3 楼整个系列不止5贴，但是现在一下都写出来, 我没那么多精力啊. 慢慢来吧. 我定期更新. 2009-5-19 22:04 0
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 4 楼好了, 仿射密码的理论介绍就到这里. 附件中为仿射密码学习的小软件. 附带源码. 希望大家用的上. 谢谢 ! 你自己講介紹到這裏的 <== 不是我講的。這些內容，我誠收了，當做是「近代密碼學及其應用--軟件加密與解密實作 (看雪學院版)」，的一部分。其它的內容，等您上繳上來再說。 2009-5-19 22:14 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 5 楼好的, 十分荣幸! 密码学这方面, 其实我也是一个初学者, 发帖的目的只是分享一下自己的一些理解. 失误之处还请大家多多指正~~ 2009-5-19 22:22 0
lingyu 雪币： 1022 活跃值： (31) 能力值： ( LV4，RANK：50 ) 在线值：发帖 29 回帖 449 粉丝 0 关注私信	lingyu 1 6 楼支持相信很多对密码学感兴趣的要这样的文章 2009-5-19 22:33 0
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 7 楼放心吧~ 有我親自背書，沒問題的。但內容可不能給我亂寫，這是真的。我會請 lingyu 大大及其他大大一起“關注”。你若表現好，我願意推荐你去 MIT 學習。 2009-5-19 22:38 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 8 楼哈哈, MIT ? 我不是在作梦吧 2009-5-19 23:43 0
whzr 雪币： 211 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 77 粉丝 1 关注私信	whzr 9 楼第一次听说“仿射密码”…… 关注中。 2009-5-20 07:46 0
玩命雪币： 7115 活跃值： (639) 能力值： (RANK：1290 ) 在线值：发帖 61 回帖 456 粉丝 75 关注私信	玩命 31 10 楼搬个板凳过来学习。。。 2009-5-20 09:58 0
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 11 楼對模的逆： Ex: 1) 11-1 mod 26 = 19，建議寫成 (11)^-1 ，或是 (11^-1)。 2) 逆，可以寫成逆(inverse element) 。 2009-5-20 14:14 0
加百力雪币： 2604 活跃值： (64) 能力值： (RANK：510 ) 在线值：发帖 86 回帖 896 粉丝 4 关注私信	加百力 12 12 楼一起来温习一下。看密码学的教材讲过，这里再重复巩固一下。密码学确实太重要了！ 2009-5-20 14:43 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 13 楼谢谢提醒, 我会注意的. 用M^-1表示M的逆矩阵的确蛮不错的, Thanks.~~ 2009-5-20 18:19 0
linhanshi 雪币： 97697 活跃值： (200819) 能力值： (RANK：10 ) 在线值：发帖 9249 回帖 27946 粉丝 452 关注私信	linhanshi 14 楼 Support. 2009-5-23 19:42 0
ygwh 雪币： 242 活跃值： (32) 能力值： ( LV2，RANK：10 ) 在线值：发帖 4 回帖 48 粉丝 0 关注私信	ygwh 15 楼谢谢楼主！ 2009-6-4 21:36 0
心静雪币： 193 活跃值： (11) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 28 粉丝 0 关注私信	心静 16 楼好好学习！顶！ 2009-6-14 16:02 0
xtjjcel 雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 3 回帖 37 粉丝 0 关注私信	xtjjcel 17 楼感谢楼主支持下去 2009-6-24 15:05 0
siwen 雪币： 235 活跃值： (25) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 51 粉丝 0 关注私信	siwen 18 楼感谢LZ，学习了。特别是怎样快速求模逆的方法。 2009-6-26 14:33 0
jmuguy 雪币： 1211 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 1 回帖 56 粉丝 0 关注私信	jmuguy 19 楼 rockinuk大大好猛啊。。。。推荐去MIT。。。。。梦啊。。。。 2009-8-25 11:04 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 20 楼那得被推荐的人有实力才行 . 所以猛是取决于双方了. 我们已经没机会了 . 年轻的你们若对密码学感兴趣的, 一定要学好数学. 这样R大才有机会推荐你们的. 2009-8-25 20:19 0
jmuguy 雪币： 1211 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 1 回帖 56 粉丝 0 关注私信	jmuguy 21 楼嗯啊。。。好好学习。。。。 2009-8-26 22:33 0
wqshandian 雪币： 117 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 17 粉丝 0 关注私信	wqshandian 22 楼讲得可以，只是我从你的文章中看不到一个反射密码的通用算法，只是简单的作介绍，而说到扩展欧几里德算法时，也只是举了个例子。个人认为对这些应该作尽详细的描述，必要时需要证明，还有在反射密码分析时需要对分析方法作具体介绍，这样才算完整介绍了反射密码。 2009-8-27 13:01 0
redou 雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 9 回帖 26 粉丝 0 关注私信	redou 23 楼 blackhat 2009上好像有人讨论了crack，看了下，E文不好，大意不过倒是理解了，有兴趣的可以看下，应该会有启发 2009-8-28 15:51 0
ILHWF 雪币： 201 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 1 粉丝 0 关注私信	ILHWF 24 楼正用着呢。。。。谢谢楼主了 2011-3-19 18:16 0
hbwazxf 雪币： 152 活跃值： (20) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 121 粉丝 0 关注私信	hbwazxf 25 楼新手学习了。。。。。。。 2011-3-19 18:27 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

jackozoo

发帖

775

回帖

680

RANK

关注

私信

他的文章

关于我们

联系我们

企业服务

看雪公众号

最新回复 (28) 1 2 ▶
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 2 楼建議可以再寫多一點~ 兩帖有點少~來個5 帖吧~~ 2009-5-19 21:52 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 3 楼整个系列不止5贴，但是现在一下都写出来, 我没那么多精力啊. 慢慢来吧. 我定期更新. 2009-5-19 22:04 0
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 4 楼好了, 仿射密码的理论介绍就到这里. 附件中为仿射密码学习的小软件. 附带源码. 希望大家用的上. 谢谢 ! 你自己講介紹到這裏的 <== 不是我講的。這些內容，我誠收了，當做是「近代密碼學及其應用--軟件加密與解密實作 (看雪學院版)」，的一部分。其它的內容，等您上繳上來再說。 2009-5-19 22:14 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 5 楼好的, 十分荣幸! 密码学这方面, 其实我也是一个初学者, 发帖的目的只是分享一下自己的一些理解. 失误之处还请大家多多指正~~ 2009-5-19 22:22 0
lingyu 雪币： 1022 活跃值： (31) 能力值： ( LV4，RANK：50 ) 在线值：发帖 29 回帖 449 粉丝 0 关注私信	lingyu 1 6 楼支持相信很多对密码学感兴趣的要这样的文章 2009-5-19 22:33 0
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 7 楼放心吧~ 有我親自背書，沒問題的。但內容可不能給我亂寫，這是真的。我會請 lingyu 大大及其他大大一起“關注”。你若表現好，我願意推荐你去 MIT 學習。 2009-5-19 22:38 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 8 楼哈哈, MIT ? 我不是在作梦吧 2009-5-19 23:43 0
whzr 雪币： 211 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 77 粉丝 1 关注私信	whzr 9 楼第一次听说“仿射密码”…… 关注中。 2009-5-20 07:46 0
玩命雪币： 7115 活跃值： (639) 能力值： (RANK：1290 ) 在线值：发帖 61 回帖 456 粉丝 75 关注私信	玩命 31 10 楼搬个板凳过来学习。。。 2009-5-20 09:58 0
rockinuk 雪币： 2096 活跃值： (100) 能力值： (RANK：420 ) 在线值：发帖 613 回帖 1939 粉丝 7 关注私信	rockinuk 8 11 楼對模的逆： Ex: 1) 11-1 mod 26 = 19，建議寫成 (11)^-1 ，或是 (11^-1)。 2) 逆，可以寫成逆(inverse element) 。 2009-5-20 14:14 0
加百力雪币： 2604 活跃值： (64) 能力值： (RANK：510 ) 在线值：发帖 86 回帖 896 粉丝 4 关注私信	加百力 12 12 楼一起来温习一下。看密码学的教材讲过，这里再重复巩固一下。密码学确实太重要了！ 2009-5-20 14:43 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 13 楼谢谢提醒, 我会注意的. 用M^-1表示M的逆矩阵的确蛮不错的, Thanks.~~ 2009-5-20 18:19 0
linhanshi 雪币： 97697 活跃值： (200819) 能力值： (RANK：10 ) 在线值：发帖 9249 回帖 27946 粉丝 452 关注私信	linhanshi 14 楼 Support. 2009-5-23 19:42 0
ygwh 雪币： 242 活跃值： (32) 能力值： ( LV2，RANK：10 ) 在线值：发帖 4 回帖 48 粉丝 0 关注私信	ygwh 15 楼谢谢楼主！ 2009-6-4 21:36 0
心静雪币： 193 活跃值： (11) 能力值： ( LV2，RANK：10 ) 在线值：发帖 2 回帖 28 粉丝 0 关注私信	心静 16 楼好好学习！顶！ 2009-6-14 16:02 0
xtjjcel 雪币： 200 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 3 回帖 37 粉丝 0 关注私信	xtjjcel 17 楼感谢楼主支持下去 2009-6-24 15:05 0
siwen 雪币： 235 活跃值： (25) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 51 粉丝 0 关注私信	siwen 18 楼感谢LZ，学习了。特别是怎样快速求模逆的方法。 2009-6-26 14:33 0
jmuguy 雪币： 1211 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 1 回帖 56 粉丝 0 关注私信	jmuguy 19 楼 rockinuk大大好猛啊。。。。推荐去MIT。。。。。梦啊。。。。 2009-8-25 11:04 0
jackozoo 雪币： 1450 活跃值： (35) 能力值： (RANK：680 ) 在线值：发帖 50 回帖 775 粉丝 3 关注私信	jackozoo 14 20 楼那得被推荐的人有实力才行 . 所以猛是取决于双方了. 我们已经没机会了 . 年轻的你们若对密码学感兴趣的, 一定要学好数学. 这样R大才有机会推荐你们的. 2009-8-25 20:19 0
jmuguy 雪币： 1211 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 1 回帖 56 粉丝 0 关注私信	jmuguy 21 楼嗯啊。。。好好学习。。。。 2009-8-26 22:33 0
wqshandian 雪币： 117 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 17 粉丝 0 关注私信	wqshandian 22 楼讲得可以，只是我从你的文章中看不到一个反射密码的通用算法，只是简单的作介绍，而说到扩展欧几里德算法时，也只是举了个例子。个人认为对这些应该作尽详细的描述，必要时需要证明，还有在反射密码分析时需要对分析方法作具体介绍，这样才算完整介绍了反射密码。 2009-8-27 13:01 0
redou 雪币： 5 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 9 回帖 26 粉丝 0 关注私信	redou 23 楼 blackhat 2009上好像有人讨论了crack，看了下，E文不好，大意不过倒是理解了，有兴趣的可以看下，应该会有启发 2009-8-28 15:51 0
ILHWF 雪币： 201 活跃值： (10) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 1 粉丝 0 关注私信	ILHWF 24 楼正用着呢。。。。谢谢楼主了 2011-3-19 18:16 0
hbwazxf 雪币： 152 活跃值： (20) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 121 粉丝 0 关注私信	hbwazxf 25 楼新手学习了。。。。。。。 2011-3-19 18:27 0
	游客登录 \| 注册方可回帖回帖表情雪币赚取及消费高级回复

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

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