tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 数学 >>

数论在密码学中的应用


本科学生毕业论文(设计)
题目(中文) :
(英文) :

数论在密码学中的应用 The Application of Number Theory in Cryptography

姓 学

名 号





200805001104 湖南科技学院数学与计算科学系 数学与应用数学 0801 班 王启春(博士)

院 (系) 专业、年级 指导教师

2012 年 5 月

1日

湖南科技学院本科毕业论文(设计)诚信声明

本人郑重声明:所呈交的本科毕业论文(设计) ,是本人在指 导老师的指导下,独立进行研究工作所取得的成果,成果不存在 知识产权争议,除文中已经注明引用的内容外,本论文不含任何 其他个人或集体已经发表或撰写过的作品成果。对本文的研究做 出重要贡献的个人和集体均已在文中以明确方式标明。本人完全 意识到本声明的法律结果由本人承担。

本科毕业论文(设计)作者签名:

二○一二年五月一日

目录
1 绪论 ......................................................................................................................... 1 1.1 引言................................................................................................................... 1 1.2 数学语言........................................................................................................... 1 2 数论 ......................................................................................................................... 2 2.1 同余................................................................................................................... 3 2.2 质数与互质....................................................................................................... 3 2.3 因数分解........................................................................................................... 4 2.4 几个定理的证明............................................................................................... 5 3 密码学 ..................................................................................................................... 6 4 RSA 算法 .............................................................................................................. 7 4.1 公开密钥........................................................................................................... 7 4.2 现行公钥 RSA 加密算法的基本思想 ............................................................. 7 4.3 公钥与密钥的产生........................................................................................... 9 4.4 加密消息........................................................................................................... 9 4.5 解密消息........................................................................................................... 9 4.6 实例说明 RSA 算法的全过程 ....................................................................... 10 4.7 签名消息......................................................................................................... 10 4.8 安全性............................................................................................................. 11 4.9 RSA 前景 ........................................................................................................ 11 5 背包原理 ............................................................................................................... 12 5.1 背包原理......................................................................................................... 12 5.2 超递增序列..................................................................................................... 13 5.3 背包系统的加密和解密方法......................................................................... 14 6 结束语 ................................................................................................................... 15 主要参考资料: ...................................................................................................... 16 致谢 .......................................................................................................................... 17

I

数论在密码学中的应用
摘要
论文介绍了一些数论的基本知识和密码学的主要思想。并着重从 RSA 算法 与背包原理算法两个方面介绍了数论在密码学中的应用。而且构造了一个简单 的数学语言体系对背包原理和 RSA 的实例讲解。 本文把数论蕴含在整个密码学的两种算法的阐述之中,其重点是现行的公 钥体制 RSA,全面的介绍了其产生,运用,安全性,发展,未来前景及局限性。

关键词: RSA 算法,背包原理,数论,密码学,公钥体制

II

The Application of Number Theory in Cryptography
Abstract
This paper introduces some basic knowledge of number theory and cryptography, Emphasize from RSA algorithm and knapsack algorithm, it will introduce the two aspects of the application of number theory in cryptography. And constructed a simple mathematical language system on the backpack principle and RSA examples to explain. In this paper, the number theory is described in all the two algorithms in cryptography, the focus is on current public key system RSA, a comprehensive introduction to the use of safety, development, future prospects and limitations.

Key words: RSA algorithm, knapsack theory, number theory,
cryptography, public key system

III

1 绪论
1.1 引言
数论是数学中最古老、 最纯粹的一个重要数学分支。 素有“数学王子” 之称的19世纪德国数学大师高斯就曾说过,数学是科学的皇后,数论是数 学的皇后。数论,顾名思义,是一门研究数字性质的学问。一般所谓的数论, 特指正整数(即自然数)的许多性质,例如同余、质数、数论函数、有限域、背包 原理等。 密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观 规律,应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码 以获取通信情报的,称为破译学。总称密码学。密码学,起初是应用于军事 信息的保密上,但是随着当今社会计算机网络的发展,尤其是电子商务的普及 与深入,密码设计在非军事领域也大有用武之地,密码已经与我们每一位息 息相关。 而密码学的发展到现在与数学,特别数学的基础数论已经密不可分, 可以说密码学是数论从理论到现实的一个应用,而数论是密码学走向更高 的基石。

1.2 数学语言
为了本文的讨论方便,现就本文涉及到的自然语言与数学语言做如下 规定; 1.本文将一个字母代替整个传输过程中的数据,也就是一个字母成立 则对于由字母构成的所有整体也成立。 2.由于文字母只有26个,本文计算过程中,为了简化,不考虑语言中 问号、惊叹号、逗号与句号等的区别,只考虑语言的停顿间隙,并一律用空格表 示,那么,组成数字语言的基本单位就有了.共27个( 2 4 ? 2 7 ? 2 5 ),将不使 用ASCII值,只使用如下表所示的字母和数学语言的简单对应如表1。

1

表1 字母 a b c d e f g h i j k l m n 二进制数 00001 00010 00011 00100 00101 00110 00111 01000 01001 01010 01011 01100 01101 01110 十进制数 1 2 3 4 5 6 7 8 9 10 11 12 13 14 字母 o p q r s t u v w x y z 空格 二进制数 01111 10000 10001 10010 10011 10100 10101 10110 10111 11000 11001 11010 00000 十进制数 15 16 17 18 19 20 21 22 23 24 25 26 0

2 数论
数论就是指研究整数性质的一门理论。整数的基本元素是素数,所以数论 的本质是对素数性质的研究。2000 年前,欧几里得证明了有无穷个素数。寻找 一个表示所有素数的素数通项公式,或者叫素数普遍公式,是古典数论最主要的 问题之一。 它是和平面几何学同样历史悠久的学科。 高斯誉之为 “数学中的皇冠” 按照研究方法的难易程度来看,数论大致上可以分为初等数论(古典数论)和高 等数论(近代数论) 初等数论主要包括整除理论、同余理论、连分数理论。它 。 的研究方法本质上说,就是利用整数环的整除性质。初等数论也可以理解为用初 等数学方法研究的数论。其中最高的成就包括高斯的“二次互反律”等。高等数 论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、算术代
2

数几何等等。下面粗略的介绍一些在本文中需要应用的数论中的知识。

2.1 同余
设m是大于1的正整数,a,b是整数,如果m│a-b,则称a,b关于模m同余,记 作a≡b(mod m),读作a同余b模m。通俗的讲就是m除a,b余数相同则a,b关于m同余。 例如5和7除以2,余数都是1,则5和7关于2同余。 同余有如下性质: (1) a ? a (m od m ) ; (2)若 a ? b (m od m ) ,则 b ? a (m od m ) ; (3)如果 a ? b (m od m ) , b ? c (m od m ) ,那么 a ? c (m od m ) ; (4)如果 a ? b (m od m ) , c ? d (m od m ) , 那么 a ? c ? b ? d (m od m ) ,
ac ? bd (m od m ) ;

(5)若 a c ? b c (m o d m ) c ! ? 0 ,则 a ? b (m od m / ( c , m )) ; (6)如果 a ? b (m od m ) 那么 a n ? b n (m o d m ) ; (7)若 a ? b (m od m ) , n | m 则 a ? b (m o d n ) ; (8)若 a ? b (m od m i ), i ? 1, 2 ? n , a ? b (m od[ m 1 , m 2 ? m n ]) , 则 其中 [ m 1 , m 2 ? m n ] 表示 m 1 , m 2 ? m n 的最小公倍数; (9)欧拉定理:设 a , m ? N , ( a , m ) ? 1, 则 a ??? m ?? ? 1(m od m ) , ? ? m ? 指模m的简 系个数, ? ? m ? ? m ? 1 ;

2.2 质数与互质
如果一个整数 (1除外) 只有1和它本身两个约数, 则这个数是质数 (即素数) 。 若两正整数p,q的最大公因子(约数)是1,则我们称p,q互质,以(p,q)=1表示之。 如 13 是质数,13 与 28 互质。 素性检测是数论中一个经典的问题 ,近代密码学的兴起给它注入了新的活 力 ,其中最重要的是素数的判定 ,特别是在素数的生成和分解。强素数的提出 源自 RSA 对 p,q 两素数的要求。 椭圆曲线公钥密码中所涉及到大特征基域的尺寸 和安全椭圆曲线的基点 的阶也需要是确定意义下的素数 ,而不是概率素数 。 目前,学术界关于素性证明的算法有两种 :一种是椭圆曲线素性证明,现已列 入 IEEE 标准 P1363 中;另一种是现行公开密钥码系统最常用的 Miller-Rabin 素数测试 。

3

( 1)素数分布定理:设 ? x ) 为小于或等于 x 的全部素数个数 ,则

lim ? x )? (
x? ?

x ln x



2)威尔逊定理:n 是素数的充要条件下有:
n-1 ? ? 1(m od n ) 。

威尔逊定理给出判定素数充要条件 ,有很高的理论价值 。但用来寻找素数 不适当 。 3)Fermat 定理(费马小定理) :关于素数还有一个 Fermat 定理。此定理给 出素数的必要条件 p ,若不满足 ,则可断定它为素数 定理内容为,若 p 是素 数 ,则对于任意的整数 a ,应有
a
p ?1

? 1(m o d p ) 。

2.3 因数分解
整数分解(质因子分解)问题是指:给出一个正整数,将其写成几个质数 的乘积。例如,给出 45 这个数,它可以分解成 32 ×5。 本文接下来要着重介绍的 RSA 算法就是一个基于大数分解的算法。而 RSA 用到都是 128bit 及以上的大数,用计算机和人脑都是很难分解的。下面给大家 介绍一种大数分解的方法让大家体验一下大数分解的难度: 几率演算法:首先选定一个简单的整数多项式 f ,如 f ( x ) ? x 2 ? 1 ,再任选
x ? x 0 并且依序计算 x j ? 1 ? f ( x j ) , j ? 0 , 1, 2? 。然后计算 q ? g c d (x j ? x k ,n ),且 ,
q ? 1, n

,若 q 可以整除 n,则 q 是 n 的一个因数。

例如:
x 0 ? 1, n ? 91, f ( x ) ? x ? 1
2

x1 ? 1 ? 1 ? 9 1
2 2

2

g cd ( x1 ? x 0 , n ) ? g cd (2 ? 1, 9 1) ? 1
5

x2 ? 2 ? 1 ? 91 x3 ? 5 ? 1 ? 9 1
2 2

g cd ( x 2 ? x1 , n ) ? g cd (5 ? 2, 9 1) ? 1 g cd ( x 3 ? x 2 , n ) ? g cd (2 6 ? 5, 9 1) ? 1
40

26

x 4 ? 26 ? 1 ? 91

gcd( x 4 ? x 3 , n ) ? gcd(40 ? 26, 91) ? 1

所以我们得到了 91 的一个质因数 7,另外一个 13 也可以用类似方法求出。 但是这还只是两位的,要是对于更大的数,我们要处理的次数就越多,它的 质因数每增加一个,计算量就成指数增加,所以即使你懂得了分解方法,要
4

用计算机去分解一个大数(128bit 及以上)要需要几十年年的时间。

2.4 几个定理的证明
1)若两正整数 p , q 互质,则可以找到二整数(不一定正) a , b 使得
ap ? bq ? 1

证明: 令 A 为含所有 x ? ap ? bq ? 0, a , b 为整数之集合,此集合显然不是空集合,因 可取 a ? b ? 1, p ? q ? 0 。令 d 为此集合中之最小者,若 d ? 1 ,则本定理得证,若
d ? 1 ,令 ap ? bq ? d ? 1 ,则任取此集中之另一数。 a ' p ? b ' q

,则我们若以 d 除

a ' p ? b 'q

,则得
a ' p ? b ' q ? ad ? r , 0 ? r ? d

代入
d ? ap ? bq

则得
( a '? a ) p ? ( b '? b ) q ? r

此 r 必为 0,否则 r 为 A 集中一小于 d 之数,与假设 d 为最小数相矛盾,因 r=0 故 d 为 A 集中任何一数之因子。因
p ? A ( a ? 1, b ? 0) q ? A ( a ? 0, b ? 1)

故 d 为 p , q 之公因子。但 p , q 之最大公因子为 1,故 d=1,定理证毕。 2)若 w 与 m 为二互质的正整数且 m ? w ,则可找到一正整数 ? 使得 w? ? 1(m od m ) 证明: 由定理知,有 a , b 二整数使得 aw ? bm ? 1 ,因 bm 为 m 之倍数,故
a w ? 1(m o d m )


a ? ?m ?? ,0 ? ? ? m

则得

5

? w ? 1(m od m ) 且 ? ? 0

因 ? 不可能为 0,故得证。 3)若 m 为质数, w 为任一与 m 互质之整数,则
w
m ?1

? 1(m od p )

证明: 先把 w 写成 w 个 1 的和,则由多项式定理知
(1 ? 1 ? 1 ? ? ? 1)
m

之展开式中除 w 个 1 之外, 都含有 m 之因子, m 为质数 m ! 中之 m 不可能消去), ( 故
w
m?

w (m o d m )

两边乘以 2)中之 a,即
a w ? 1(m o d m )


w
m ?1

? 1(m o d m )

本定理证毕。

3 密码学
密码学是研究编制密码和破译密码的技术科学。 研究密码变化的客观规律, 应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码以获取通信情 报的,称为破译学。总称密码学。 密码学是研究如何隐密地传递信息的学科。 在现代特别指对信息以及其传输 的数学性研究,常被认为是数学和计算机的分支,密码学的首要目的是隐藏信息 的涵义,并不是隐藏信息的存在。密码学也促进了计算机科学,特别是在于电脑 与网络安全所使用的技术,如访问控制与信息的机密性。密码学已被应用在日常 生活:包括银行卡的优盾、电脑使用者存取密码、qq 等网络应用密码等等。 密码是通信双方按约定的法则进行信息特殊变换的一种重要保密手段。 依照 这些法则,变明文为密文,称为加密变换;变密文为明文,称为脱密变换。密码 在早期仅对文字或数码进行加、 脱密变换, 随着通信技术的发展, 对语音、 图像、 数据等都可实施加、脱密变换。

6

密码学是在编码与破译的斗争实践中逐步发展起来的, 并随着先进科学技术 的应用,已成为一门综合性的尖端技术科学。它与语言学、数学、电子学、声学、 信息论、计算机科学等有着广泛而密切的联系。它的现实研究成果,特别是各国 政府现用的密码编制及破译手段都具有高度的机密性。

4

RSA 算法

4.1 公开密钥
进行明密变换的法则,称为密码的体制。指示这种变换的参数,称。 为密钥。它们是密码编制的重要组成部分。密码体制的基本类型可以分为 四种:错乱即按照规定的图形和线路,改变明文字母或数码等的位置成为 密文;代替即用一个或多个代替表将明文字母或数码等代替为密文;密本 即用预先编定的字母或数字密码组,代替一定的词组单词等变明文为密文; 加乱即用有限元素组成的一串序列作为乱数,按规定的算法,同明文序列 相结合变成密文。以上四种密码体制,既可单独使用,也可混合使用 ,以 编制出各种复杂度很高的实用密码。 公开密钥算法是在1976年由当时在美国斯坦福大学的迪菲(Diffie) 和赫尔曼(Hellman)两人首先发明的(论文”New Direction in Cryptography”)。但目前最流行的RSA是1977年由MIT教授Ronald L.Rivest,Adi Shamir和Leonard M.Adleman共同开发的,分别取自三名数学 家的名字的第一个字母来构成的。

4.2 现行公钥 RSA 加密算法的基本思想
公钥加密算法中使用最广的是RSA。RSA使用两个密钥,一个公共密钥, 一个专用密钥。因为公钥是公开对外发布的,所以想给私钥持有者发送信息的 人都可以取得公钥,用公钥加密后,发送给私钥持有者,即使被拦截或窃取,没 有私钥的攻击者也无法获得加密后的信息,可以保证信息的安全传输 另外,先 用私钥加密,再用公钥解密,可以完成对私钥持有者的身份认证,因为公钥只能 解开有私钥加密后的信息。 虽然公钥和私钥是一对互相关联的密钥,但是并不 能从两者中的任何一把,推断出另一把。如用其中一个加密,则可用另一个解 密,密钥长度从40到2048bit可变,加密时也把明文分成块,块的大小可变, 但不能超过密钥的长度,RSA算法把每一块明文转化为与密钥长度相同的密 文块。密钥越长,加密效果越好,但加密解密的开销也大,所以要在安全 与性能之间折衷考虑,一般64位是较合适的。RSA的一个比较知名的应用是
7

SSL,在美国和加拿大SSL用128位RSA算法,由于出口限制,在其它地区(包 括中国)通用的则是40位版本。 下面用一个简单的示意图,帮助大家理解基于RSA算法的数据传输(加密与 解密)过程。

基于 RSA 算法的数据传输过程 图 3.1
数据传送方的数据

加密 RSA 算法

数据接收方的公钥

加密后的数据

解密 RSA 算法

数据接收方的私钥

数据接收方获得原始数据

从图3.1中我们可以看出所谓的公开密钥密码体制(下文通常默认指RSA) 就是使用不同的加密密钥与解密密钥(两者都由数据接收者持有,公钥是公 开的,而私钥是接收者所独有的)。RSA算法是第一个能同时用于加密和数 字签名的算法,也易于理解和操作。RSA是被研究得最广泛的公钥算法,从 提出到现在的三十多年里,经历了各种攻击的考验,逐渐为人们接受,普 遍认为是目前最优秀的公钥方案之一。
8

在公开密钥密码体制中,加密密钥(即公开密钥)PK是公开信息,而 解密密钥(即秘密密钥)SK是需要保密的。加密算法E和解密算法D也都是 公开的。虽然秘密密钥SK是由公开密钥PK决定的,但却不能根据PK计算出 SK。

4.3 公钥与密钥的产生
假设A给B传送一个消息 m ,A可以用以下的方式来产生一个公钥和一个私 钥: ⑴.根据欧拉函数,不大于 N 且与 N 互质的整数个数为 ( p ? 1)( q ? 1) ⑵.选择一个整数 d 与 ( p ? 1)( q ? 1) 互质,并且 e 小于 ( p ? 1)( q ? 1) ⑶.用以下这个公式计算 e : ( d * e ) ? 1(m od(( p ? 1)( q ? 1))) ⑷.将 p 和 q 的记录销毁。
( N , e ) 是公钥, ( N , d )

是私钥。 ( N , d ) 是秘密的。A 将她的公钥 ( N , e ) 传给 B,

而将她的私钥 ( N , d ) 藏起来。

4.4 加密消息
因为 B 知道产生的 N 和 e 。 他使用起先与 A 约好的格式将 m 转换为一个小于

N 的整数 n,比如他可以将每一个字转换为这个字的 Unicode 码,然后将这些数
字连在一起组成一个数字。假如他的信息非常长的话,他可以将这个信息分为几 段,然后将每一段转换为 n。用下面这个公式他可以将 n 加密为 c:
n ? c (m o d N ) 。
e

计算 c 并不复杂。B 算出 c 后就可以将它传递给 A。

4.5 解密消息
A 得到 B 的消息 c 后就可以利用她的密钥 d 来解码。他可以用以下这个公式 来将 c 转换为 n:
c
d

? n (m o d N ) 。

得到n后,他可以将原来的信息m重新复原。 解码的原理是
9

c ?n
d

e?d

(m od N )

以及
e * d ? 1(m od( p ? 1)) 和 e * d ? 1(m od( q ? 1))



由费马小定理可证明(因为p和q是质数)
n
e?d

? n (m o d p )

和 n e ? d ? n (m o d q ) 。 。

这说明(因为p和q是不同的质数,所以p和q互质)
n
e?d

? n (m o d p q )

4.6 实例说明 RSA 算法的全过程
下文将通过一个数据传输假设(此假设省略了加密过程中的数据转换 过程)为大家讲解RSA加密算法的实现。 现在假设数据发送方(A)要给数据接受方(B)发送一个私人数据sa, 按照表1不烦把sa对应成数学语言1901(十进制对应)。比如传输1901的时候 我们选取p=47,q=59则n=2773。不妨选择d=157,则根据4.3中⑶可以算出e=17。把 明文1901自乘e(=17)次,并模n(=2773)得到余数1281,就是密文。这就是加 密的全过程了,而解密的时候我们接收方已经知道了密文1281,密钥d=157以及 公钥n=2773利用4.5中的公式, 也就是说我们只要把 1 2 8 11 5 7 模去若干个n即可得到 明文1901,再把1901根据表1翻译成自然语言就是sa。 这里牵涉到两个很大的数的同余问题,可以参考一下高等教育出版社的《竞 赛数学教程》第二版。以第一个计算 1 9 0 11 7 除以2773的余数为例,很容易看出
1 9 0 1 ? 5 8 2 (m o d 2 7 7 3) ,进而 1 9 0 1 ? 5 8 2 ? 4 1 8(m o d 2 7 7 3) 进而可以算得
2 4 2 16

1901

? 2 5 ? 6 2 5(m o d 2 7 7 3)
2

,从而 1 9 0 11 7 ? 6 2 5 ? 1 9 0 1 ? 1 2 8 1(m o d 2 7 7 3) ,这样我

们就得到密文了。

4.7 签名消息
RSA也可以用来为一个消息署名。假如甲想给乙传递一个署名的消息的话, 那么她可以为她的消息计算一个散列值(Message digest),然后用她的密钥 (private key)加密这个散列值并将这个“署名”加在消息的后面。这个消息只 有用她的公钥才能被解密。乙获得这个消息后可以用甲的公钥解密这个散列值, 然后将这个数据与他自己为这个消息计算的散列值相比较。假如两者相符的话, 那么他就可以知道发信人持有甲的密钥, 以及这个消息在传播路径上没有被篡改 过。

10

4.8 安全性
假设偷听者乙获得了甲的公钥N和e以及丙的加密消息c,但她无法直接获得 甲的密钥d。要获得d,最简单的方法是将N分解为p和q,这样她可以得到同余方 程
( d * e ) ? 1(m od(( p ? 1)( q ? 1)))

并解出d,然后代入解密公式
c ?n
d e?d

(m od N )

导出n(破密)。但至今为止还没有人找到一个多项式时间的算法来分解一个大 的整数的因子,同时也还没有人能够证明这种算法不存在。 至今为止也没有人能够证明对N进行因数分解是唯一的从c导出n的方法,但 今天还没有找到比它更简单的方法。(至少没有公开的方法。)因此今天一般认 为只要N足够大,那么黑客就没有办法了。假如N的长度小于或等于256位,那么 用一台个人电脑在几个小时内就可以分解它的因子了。1999年,数百台电脑合作 分解了一个512位长的N。今天对N的要求是它至少要1024位长。 1994年彼得·秀尔(Peter Shor)证明一台量子计算机可以在多项式时间内 进行因数分解。假如量子计算机有朝一日可以成为一种可行的技术的话,那么秀 尔的算法可以淘汰RSA和相关的衍生算法。(即依赖于分解大整数困难性的加密 算法) 假如有人能够找到一种有效的分解大整数的算法的话, 或者假如量子计算机 可行的话,那么在解密和制造更长的钥匙之间就会展开一场竞争。但从原理上来 说RSA在这种情况下是不可靠的。

4.9 RSA 前景
针对RSA最流行的攻击一般是基于大数因数分解。1999年,RSA-155(512 bits)被成功分解,花了五个月时间(约8000 MIPS年)和224 CPU hours在一台 有3.2G中央内存的Cray C916计算机上完成 。 2002年,RSA-158也被成功因数分解。 RSA-158表示如下: 39505874583265144526419767800614481996020776460304936454139376051 579355626529450683609 72784246821953509354430587049025199565533571020979922648497794944 2955603 =

11

338849583746672139436839320467218152281583036860499304808492584055528 1177× 11658823406671259903148376558383270818131012258146392600439520994 131344334162924536139 2009年12月12日,编号为RSA-768 (768 bits, 232 digits)数也被成功分 解[1]。这一事件威胁了现通行的1024-bit密钥的安全性,普遍认为用户应尽快 升级到2048-bit或以上。 RSA-768表示如下: 12301866845301177551304949583849627207728535695953347921973224521 5172640050726 36575187452021997864693899564749427740638459251925573263034537315 4826850791702 61221429134616704292143116022212404792747377940806653514195974598 56902143413 = 3347807169895689878604416984821269081770479498371376856891 2431388982883793878002287614711652531743087737814467999489× 6032283815739666511279233373417143396810270092798736308917 尽管这样RSA加密在相当一段时间内还是很有市场的,除非量子计算机真正 的问世,还有就是RSA由于需求的位数越来越高,计算的速度也会越来越慢,对 计算机的要求也会越高,个人认为终有被取代的一天,而且其中新加密方法也要 必不可少的运用到数学的思想!

5 背包原理
5.1 背包原理
设想有一个长方体形状的背包,里面恰好装满一组大小不等、形状各 异的 积木块。又,旁边还有一堆积木块。如果把背包里的积木块倒在这一堆积木块里 搅匀,那么再从中挑出一组积术块使它们恰好装满背包是十分困难的。类似的数 学问题可表述为 : 背包问题: 设 A ? ( a1 , a 2 , a 3 ...a n ) ,n 是正整数, a n 也是正整数。问是否存在
i1 , i 2 , ...i k (1 ? i j ? n , j ? 1, 2, ...k )

使
a ?

?a
j ?1

k

ij

A 称为背包矢量或背包序列。

12

这里 A 就像那一大堆积木块,a 是背包,能不能从 A 中挑出

a i , a i ...a i
1 2

恰好
k

装满 n 是很难判断的。用专业语言来说,这是一个 NP 完全问题(见本节后注 1)。 不过对于某些背包矢量 A,上述问题是容易解决的,这就是矢量 A 构成超递 增数列的情形。

5.2 超递增序列
定义 1 正整数序列 a1 , a 2 .... 叫超递增序列,如果
ai ?

?a
i ?1

i ?1

j

, i ? 2, 3, ....

这一定义对有限序列也适用。通俗地说,每一项都大于它前面各项之和的正整数 序列叫超递增序列。下面就是两个超 递增序列:
A ? (1, 2, 5, 9, 2 0, 4 1) , B ? (103,107, 211, 430, 863,1718, 3449, 6907,1380 7, 27610) 。

对于超递增序列 A 而言,如果给定了一个正整数 a.是很容易判断 a 是否能 表示为 A 中的若 干个项之和的。比如序列 A ,a=52。因为 n>41,41 必须被选 中,否则其它各项全选也不 够 41,从而更达不到 52。然后算出 52—41:11。 因为 11 恰大于 A 中的 9,9 必须被选中, 否则前面各项加起来也不到 9,更达 不到 11。同理,算出 11—9=2 正好是 A 中的项,这样就 得到 52=41+9+2。再如 序列 B,a=10000。如果 a 能表示为 B 中的若干项之和,那么 从 a 恰大于 6907 知 6907 是一个加项,然后算出 10000—6907=3093。3093 恰大于 B 中的 1718, 3039—1718=1375,1375—863=512,512—430=82。因为 82 不是 B 中的项,所以 a=10000 不能表示为 B 中的若干项之和。 背包系统就是将超递增序列用于秘密地传递数字语言的一种密码系统。 事实 上,只要会 秘密地传送一个字母,也就会传送整个语言了。而由表 1 知一个字母可以看
成一个 5 位的二进制数,比如 i 可看成 01001。选取一个超递增序列 A ? (1, 2, 5, 9, 2 0, 4 1) 把 i 也想成一个矢量 ? ? (0,1, 0, 0,1) 并作 A 与 ? 的内积。
A ? ? ? (1, 2, 3, 9, 20) ? (0,1, 0, 0,1) ? 22



基于超递增序列 A 就可以把 i 以数字 22 的形式发送给对方, 对方收到数字 22 后,如果他 也知道这个超递增序列 A,就很容易算出(0,1,0,0,1)这个序 列从而可以恢复出文字来。如果敌方截获了数字 22,因为他不知道 A,也就恢复 不出 i 来。但以上所述不是真正的背包系统。在实用的背包系统中,序列 A 的长 度 远远大于 5,可以达到 100。同时序列 A 经过用数论方法进行变换后可将所 得的非超递增序列 B 公诸与众,但控制一些秘钥仅为友方所知。
13

5.3 背包系统的加密和解密方法
用机器语言作加密对象,以传送两个英文字母为例进行说明。为了方便,不 妨取 i 。 (字母 i 和空格) 加密方法 之和,则 选取一个超递增序列 A ? ( a1 , a 2 , ...a n ) 比如 A 为前文中所给出的

以 A ? B ? (103,107, 211, 430, 863,1718, 3449, 6907,1380 7, 27610) 。

? A 记 A 中各项

?

A

=55205。取整数 m 使 m ?

? A ,比如取 m =55207。再取整 数 t

使 1 ? t ? m 且 与 m 互素,即 ( m , t ) ≡1,比如取 t=25236。用 t 乘 A 的各项后再 用 m 去除所得各项,以 C 记所得余数依次构成的序列,即, C ? ( c1 , c 2 , ...c n ) 这里的
cn

等于 t a n 除以 m 所得的余数。经计算得
C ? (4579, 50316, 24924, 30908, 27110,17953, 3273 2,16553, 22075, 53620)

这个 C 可以公之于众,友方敌方都知道,但请注意 C 已经不是超递增序列了。 设 ? 为待传送的 i (i 和空格),由表 1 知 ? ? (0,1, 0, 0,1, 0, 0, 0, 0, 0) (二进制

对应) 。将 ? 与 C 作内积得 B ? ? ? 77426 。这个 77426 就是密文,敌方截获了也 很难从 B 和口算出 ? ,因为 C 已经不是超递增的了,正像想从一大堆积木块中找 出恰好装满背包的那些积木块一样。当 n=100 时,如果不借助其它数学理论 , 用计算机去试探性地破译背包系统得花上 30 年的时间 ! 解密方法 友方在收到信息 ? 后是容易基于 C 而恢复出 ? 来的, 因为 t 与

m 这两个密钥是 通知了友方的。利用 t 和 m,根据公式 u t ? 1(m o d m ) ,可以很快 算出 u=1061。有了 u “就可以从 C 中恢复出超递增序列 A 来,用 u 去乘 C 的各 项再摸去若干个 m 记得 A。下面以 C 的第一项 4579 为例,因为
u ? 4579 ? 4858319 ? 88 ? 55207 ? 103

所以 A 的第一项是 103。同理可以求得 A 的其他各项。现在我们知道了 A 还有 t 与 m 就可以算出非递增序列 C,然后进而求出 ? ,这些只要对加密方法进行逆运 算就可以很快得到。再把 ? 机器语言,翻译出来即可。 注 1: NP 完全问题,是世界七大数学难题之一。 NP 的英文全称是 Non-deterministic Polynomial 的问题, 即多项式复杂程度的非确定性问题。 简单的写法是 NP=P?, 问 题 就 在 这 个 问 号 上 , 到 底 是 NP 等 于 P , 还 是 NP 不 等 于 P 。 NP 就是 Non-deterministic Polynomial 的问题,也即是多项式复杂程度的非确定性问

14

题。 有些计算问题是确定性的,比如加减乘除之类,你只要按照公式推导,按 部就班一步步来,就可以得到结果。但是,有些问题是无法按部就班直接地计算 出来。比如,找大质数的问题。有没有一个公式,你一套公式,就可以一步步推 算出来,下一个质数应该是多少呢?这样的公式是没有的。再比如,大的合数分 解质因数的问题,有没有一个公式,把合数代进去,就直接可以算出,它的因子 各自是多少?也没有这样的公式。这种问题的答案,是无法直接计算得到的,只 能通过间接的“猜算”来得到结果。这就是非确定性问题。而这些问题的通常有 个算法,它不能直接告诉你答案是什么,但可以告诉你,某个可能的结果是正确 的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法,假如可以 在多项式时间内算出来,就叫做多项式非确定性问题。而如果这个问题的所有可 能答案,都是可以在多项式时间背包问题实际上是一个 NP 完全问题内进行正确 与否的验算的话, 就叫完全多项式非确定问题完全多项式非确定性问题可以用穷 举法得到答案, 一个个检验下去, 最终便能得到结果。 但是这样算法的复杂程度, 是指数关系,因此计算的时间随问题的复杂程度成指数的增长,很快便变得不可 计算了。

6 结束语
在着手这篇论文的时候作者一直都是力求用最简单的文字向大家展示数论 在密码学中的两方面应用。其中 RSA 算法是先摆理论后举事例,背包原理是把理 论蕴含于事例之中。相信数论在密码学中的应用也远远不止这些,比如美国国安 局的 SHA 算法体系, 但是不管密码学以后如何发展我深信其与数论将更加息息相 关!

15

主要参考资料:

[1] 柯召,孙琦.数论讲义[M].北京:高等教育出版社, 2003:27-175. [2] 黄文璋. 数学欣赏[M].北京:中国统计出版社, 2001:22-33. [3] Yan S Y. Number Theory for Computing 2nd Edition[M].New York: Springer-Verlag, 2002:23-25. [4] Neal koblitz.A course in Number Theory and Cryptography[M]. New York: Springer-Verlag,1987:30-45. [5] Rosen K.H. Elementary Number Theory and Its Applications[M]. 北京:机械 工业出版社(影印版),2005:11-27. [6] Song Y. Yan. Number Theory for computing[M].New York:Springer-Verlag, 2002:67-80. [7] 温巧燕 ,钮心忻,杨义先.现代密码学中的布尔函数[M]. 北京:科学出版 社,2000:56-60. [8] 丁存生 ,肖国镇. 流密码学及其应用[M].北京:国防工业出版 社,1994:23-29. [9] 王国俊.数论在密码学中的应用[J].工程数学学报,2002: 19(1):07-14. [10]张福泰. 可验证秘密分享及其应用研究[D] . 西安:西安电子科技大 学,2001. [11]杨义先,林须端.编码密码学[M]. 北京:人民邮电出版社,1993:31-35. [12]刘木兰.中国学术期刊数学在密码中的某些应用[DB/OL]. http://www.gdnetlib.edu.cn/qkw.htm , 1985. [13]周师亮.密码学算法[J].电视技术知识之窗.1997,8:25—36. [14]于秀源,王小云.复合加密的公开密钥码系统[J].杭州师范学院学报.1990, 3:1—4.

16

致谢

本文完成得到王启春老师的悉心指导,王老师虽然工作繁忙,但是仍从选 题、查资料到写论文过程中碰到的具体困难都一一予以帮助,使我在写论文的过 程中避免了很多不足之处。在结笔之际,给予王老师我最真挚的谢意,同时感谢 许多对我提出宝贵意见的同学和老师! 其中需要特别指出的是我们的班主任龚罗中老师,也在百忙之中给与我指 点与许多建设性的意见,让我更好的完成了论文。还有谢谢数学系的所有教师, 谢谢他们在这四年中为我们所做的一切,他们不求回报,无私奉献的精神很让我 感动,再次向他表示由衷的感谢。在这四年的学期中结识的各位生活和学习上的 挚友让我得到了人生最大的一笔财富。在此,也对他们表示衷心感谢。 谢谢我的父母,没有他们辛勤的付出也就没有我的今天,在这一刻,将最崇 高的敬意献给你们! 本文参考了大量的文献资料,在此,向各学术界的前辈们致敬! 最后,向人类文明的不断发展致敬!

17



推荐相关:

[feiq]关于数论密码的综述

关于数论密码的综述潘上 电气 093 0815012127 摘要: 摘要:本文主要介绍了数论的概念,以及在密码学中的应用,同时分析其发展趋 势,介绍几种常用的算法,DHM,RSA 体制...


数论应用

(3)数论的应用(特别是在密码学中的 应用)以及超越数和代数数的基本知识。除了个别内容外,对于学生来说,这一部分都属于新的概念或 命题,自学是比较困难的。因此...


数论与密码学报告

数论与密码学报告_数学_自然科学_专业资料。包含多种数论算法和密码学算法的C程序...数论在密码的应用 25页 免费 数论密码 5页 1下载券 生命科学中的数学 14...


2011年上学期数论与密码学基础试卷及答案

中南大学数学院2011年上学期数论密码学基础试卷及答案中南大学数学院2011年上学期...5 D. 33 3.下列数中,找出对模 7 的指数最大的 D. 6 4.设原文为 ...


2010数论与密码学基础A

数论在密码学中的应用 5页 2财富值 数论在密码上的应用 25页 免费 高级密码学数论初步 53页 免费 密码学试卷 6页 免费如要投诉违规内容,请到百度文库投诉中心...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com