探析初等数论基本知识在密码学中的应用

2014-05-09东北大学理学院沈阳110819

山东工业技术 2014年21期

（东北大学理学院, 沈阳 110819）

一次同余方程、二次剩余是初等数论中基本的理论，本文分别讨论了它们在图像加密和文本加密中的应用。

一次同余方程；二次剩余；图像加密；文本加密

1 预备知识

随着信息技术特别是网络技术的快速发展，图像、视频，声音等多媒体信息在网络上随处可见。人们在网络不断传送，共享着这些信息，在这些信息的传送过程中，通信双方都希望以一种安全的方式在非安全通信信道传送。密码学的根本的目的是要使通信双方以一种非授权用户不能理解的通信方式在不安全信道上通信。需要加密的信息被称为明文，用M或者P表示，它可能是文本，图像，语音信息或者视频信息。用某种方法伪装消息以隐藏它的内容的过程称为加密，加密后的没有实际意义的信息称为密文，密文用C表示，加密函数对明文进行加密得到密文，同样利用解密函数将密文转变为明文的过程称为解密。明文通过加密解密之后，明文消息得到恢复。初等数论主要包括整除、同余式、二次剩余和连分数等。信息技术特别是密码学的发展，给数论的发展注入了新的发展活力，数论这门纯之又纯的数学迎来了新的发展历程，本文以数论中的两个基本知识为例，探讨数论在密码学和信息安全中的应用。

2 一次线性同余方程及其在图像加密中的应用

同余方程是同余理论中的核心内容，是应用同余思想来研究整数问题的有力工具。一次同余方程是最基本的同余方程，即形如：ax≡b（modm）的方程，将其简单变形得到加密函数：C（x）≡ax+b（modm），其中x是明文，C（x）是密文。若满足（a,m）≡1，则其解密函数如下：D（C（x））≡a-1（ax+b（modm）-b）（modm）≡a-1（ax+b-b（modm）≡a-1ax≡x（modm），其中a-1,a满足a-1a≡1（modm）。将其应用于图像加密，具体过程描述如下：

（1）将明文图像按照从左到右，从上到下的顺序转为一维序列，并利用Logistic混沌映射对其进行置乱，得到置乱后的一维明文序列：p={p1,p2,…,phxw},这里h,w是明文图像的高和宽。

（2）对于每个pi，计算其密文：C（x）≡api+b（mod256），其中（a,256）=1

（3）对于明文图像（图1），利用上述算法其加密效果如图2，

图1 明文图像Elain

图2 密文图像

显然，明文信息得到了很好的隐藏。

3 二次剩余及其在文本加密中的应用

二次剩余是数论的基本概念之一。若（a,m）=1，方程x2≡a（modm）有解，则称a是模m的二次剩余，否则称a是模m的二次非剩余。为了研究二次剩余在密码学中的应用，首先介绍几个相关的概念。

利用Legendre符号，我们又给出了Jacobi符号的定义：对任意给定的整数满足（a,n）=1,n的素数分解表达式为n=，则Jacobi符号为Legendre符号的乘积：

若a是模n的二次剩余,记为a∈Qn ,二次剩余问题可以描述为，给定正整数a和n，确定a∈Qn是否成立，求解二次剩余问题等价于求解n的素因式分解，这在计算上是不可行的。

（1）设n=rs,其中r,s是素数，其大小大约相同，作为私钥保存。

（3）对于给定的文本序列中的每一个元素gi，转换为0～25之间的整数，然后再转化为一个二进制序列{b1,b2,…,b8} 对每个bk，k=1,…8,我们随机选择某个剩余类中的元素tk，计算

这样，能保证同一个明文得到不同的密文，从而得到其加密序列{ci1,ci2,…ci8}。

取明文序列18,06,23,18，其对应的明文比特序列为：00010010,00000110,00010111, 00010010。利用上述加密算法，其密文为：100 82 16 127 130 22 140 81, , 56 82 49 56 1 40 140 114, 36 75 104 134 1 129 117 120, 126 48 49 134 81 4 43 16。

从加密过程可以看出，对于同样的明文18，加密之后，得到了不同的加密序列，加密效果较好。对应的解密过程如下：

（1）对于每一个整数密文cij，i=1…，8N，j=1,… ,8其中8N是

密文比特序列的长度。计算Legendre符号：