基于加密和解密的二维条形码的实现

摘要 本文介绍了基本的条码知识及一些数据加密与解密的算法,阐述了二维条码的相关概念、特点、分类、及其应用前景。重点在于二维条码的加密与解密的实现。具体阐述了RSA算法的原理,并附有源程序说明其加密和解密方法。

关键词 二维条码;RSA算法;加密;解密

中图分类号 TP391.4 文献标识码 A文章编号 1674-6708(2010)16-0114-02

1 二维条码的简介

1.1 二维条码的概念

二维条码/二维码 (2-dimensional bar code) 是用某种特定的几何图形按一定规律在平面(二维方向上)分布的黑白相间的图形记录数据符号信息,在代码编制上利用构成计算机内部逻辑基础的“0”、“1”比特流,使用若干个与二进制相对应的几何形体来表示文字数值信息,通过图象输入设备或光电扫描设备自动识读以实现信息自动处理。具有条码技术的一些共性:每种码制有其特定的字符集;每个字符占有一定的宽度;具有一定的校验功能等。同时,还具有对不同行的信息自动识别功能、及处理图形旋转变化等特点。

二维条码/二维码能够在横向和纵向两个方位同时表达信息,因此能在很小的面积内表达大量的信息。

1.2 二维条码/二维码的特点

1)高密度编码,信息容量大,可容纳多达1 850个大写字母或2 710个数字或1 108个字节,或500多个汉字,比普通条码信息容量约高几十倍;

2)编码范围广。该条码可以把图片、声音、文字、签字、指纹等可以数字化的信息进行编码,用条码表示出来;可以表示多种语言文字;可表示图像数据;

3)容错能力强,具有纠错功能。这使得二维条码因穿孔、污损等引起局部损坏时,照样可以正确得到识读,损毁面积达50%仍可恢复信息;

4)译码可靠性高。它比普通条码译码错误率百万分之二要低得多,误码率不超过千万分之一;

5)可引入加密措施,保密性、防伪性好;

6)成本低,易制作,持久耐用;

7)条码符号形状、尺寸大小比例可变;

8)二维条码可以使用激光或CCD阅读器识读。

1.3 二维条码/二维码的分类

二维条码/二维码可以分为堆叠式/行排式二维条码和矩阵式二维条码。堆叠式/行排式二维条码形态上是由多行短截的一维条码堆叠而成;矩阵式二维条码以矩阵的形式组成,在矩阵相应元素位置上用“点”表示二进制“1”, 用“空”表示二进制“0”,由“点”和“空”的排列组成代码。

1.3.1 堆叠式/行排式二维条码

堆叠式/行排式二维条码(又称堆积式二维条码或层排式二维条码),其编码原理是建立在一维条码基础之上,按需要堆积成二行或多行。它在编码设计、校验原理、识读方式等方面继承了一维条码的一些特点,识读设备与条码印刷与一维条码技术兼容。但由于行数的增加,需要对行进行判定,其译码算法与软件也不完全相同于一维条码。有代表性的行排式二维条码有:Code 16K、Code 49、PDF417等。

1.3.2 矩阵式二维码

矩阵式二维条码(又称棋盘式二维条码)它是在一个矩形空间通过黑、白像素在矩阵中的不同分布进行编码。在矩阵相应元素位置上,用点(方点、圆点或其他形状)的出现表示二进制“1”,点的不出现表示二进制的“0”,点的排列组合确定了矩阵式二维条码所代表的意义。矩阵式二维条码是建立在计算机图像处理技术、组合编码原理等基础上的一种新型图形符号自动识读处理码制。具有代表性的矩阵式二维条码有:Code One、Maxi Code、QR Code、 Data Matrix等。

2 RSA算法

现在网络上、银行系统、军事情报等许多领域用处非常广泛的加密算法。该算法于1977年由美国麻省理工学院mit(massachusetts institute of technology)的ronal rivest,adi shamir和len adleman3位年轻教授提出,并以3人的姓氏rivest,shamir和adlernan命名为RSA算法。该算法利用了数论领域中合数无法高效分解为两个固定质数的理论原理。与diffie-hellman算法相比,RSA算法无须收发双方同时参与加密过程,且非常适合于电子函件系统的加密。

2.1 RSA算法

1)密钥配制。假设m是想要传送的报文,现任选两个很大的质数p与q,使得:n = p * q (2-1);

选择正整数e,使得e与(p-1)(q-1)互质;这里(p-1)(q-1)表示二者相乘。再利用辗转相除法,求得d,使得:e * d = 1 ( mod ( p - 1 ) * ( q - 1 ) )(2-2);

其中x mod y是整数求余运算,其结果是x整除以y后剩余的余数,如5ψ(6) mod 6 = 52 mod 6= 25 mod 6 =1。这样得:

(e,n),是用于加密的公共密钥,可以公开出去;以及

(d,n),是用于解密的专用钥匙,必须保密。

2)加密过程:使用(e,n)对明文m进行加密,算法为:ci = mi^e ( mod n ) ( a )(2-3);这里的c即是m加密后的密文。

3)解密过程:使用(d,n)对密文c进行解密,算法为:mi = ci^d ( mod n ) ( b ) (2-4); 求得的m即为对应于密文c的明文。

2.2 RSA公共密钥加密算法的核心是欧拉(euler)函数ψ

对于正整数n,ψ(n)定义为小于n且与n互质的正整数的个数。例如,ψ(6) = 2,这是因为小于6且与6互质的数有1和5共两个数;再如ψ(7) = 6,这是因为互质数有1,2,3,5,6共6个。

欧拉在公元前300多年就发现了ψ函数的一个十分有趣的性质,那就是对于任意小于n且与n互质的正整数m,总有mψ(n) mod n = 1。例如,5ψ(6) mod 6 = 52 mod 6= 25 mod 6 =1。也就是说,在对n求余的运算下,ψ(n)指数具有周期性。

当n很小时,计算ψ(n)使用穷举法即可求出;但当n很大时,计算ψ(n)就十分困难了,其运算量与判断n是否为质数的情况相当。不过在特殊情况下,利用ψ函数的两个性质,可以极大地减少运算量。

性质2.2.1:如果p是质数,则ψ(p) = (p-1)。

性质2.2.2:如果p与q均为质数,则ψ(p・q) = ψ(p)・ψ(q) = (p-1)(q-1)。

RSA算法正是注意到这两条性质来设计公共密钥加密系统的,p与q的乘积n可以作为公共密钥公布出来,而n的因子p和q则包含在专用密钥中,可以用来解密。如果解密需要用到ψ(n),收信方由于知道因子p和q,可以方便地算出ψ(n) = (p-1)(q-1)。如果窃听者窃得了n,但由于不知道它的因子p与q,则很难求出ψ(n)。这时,窃听者要么强行算出ψ(n),要么对n进行因数分解求得p与q。因此,窃密者很难成功。

2.3RSA算法的工作原理:

1)密钥配制。设m是要加密的信息,任选两个大质数p与q;选择正整数e,使得e与ψ(n) = (p-1)(q-1)互质。

利用辗转相除法,计算d,使得ed mod ψ(n) = 1,即ed = kψ(n) +1,其中k为某一正整数。

公共密钥为(e,n),其中没有包含任何有关n的因子p和q的信息。

专用密钥为(d,n),其中d隐含有因子p和q的信息。

2)加密过程。使用公式(2-3)对明文m进行加密,得密文c。

3)解密过程。使用(d,n)对密文c进行解密,计算过程为:

cd mod n = (me mod n)d mod n

= med mod n

= m(kψ(n) + 1) mod n

= (mkψ(n) mod n)・(m mo d n)

= m

m即为从密文c中恢复出来的明文。

例如,假设我们需要加密的明文代码信息为m = 14,则:

选择e = 3,p = 5,q = 11;

计算出n = p・q = 55,(p-1)(q-1) = 40,d = 27;

可以验证:(e・d) mod (p-1)(q-1) = 81 mod 40 = 1;

加密:c = me mod n = 143 mod 55 = 49;

解密:m = cd mod n = 4927 mod 55 = 14。

2.4 关于RSA算法的说明

1)要求e与(p-1)(q-1)互质,是为了保证 ed mod (p-1)(q-1)有解。

2)实际操作时,通常先选定e,再找出并确定质数p和q,使得计算出d后它们能满足公式(2-3)。常用的e有3和65 537,这两个数都是费马序列中的数。费马序列是以17世纪法国数学家费马命名的序列。

3)在RSA算法中,n的长度是控制该算法可靠性的重要因素。目前,129位、甚至155位的RSA加密勉强可解,但大多数加密程序均采用231、308甚至616位的RSA算法,因此RSA加密还是相当安全的。

据专家测算,攻破512位密钥RSA算法大约需要8个月时间,而一个768位密钥RSA算法在2004年之前无法攻破。现在,在技术上还无法预测攻破具有2 048位密钥的RSA加密算法需要多少时间。美国lotus公司悬赏1亿美元,奖励能破译其domino产品中1 024位密钥的RSA算法的人。从这个意义上说,遵照set协议开发的电子商务系统是绝对安全的。

3 加密二维条码的生成和识别(以烟草上的二维条码为例)

3.1 加密二维条码的生成

1)将准运证或专卖证上的固有系统和特征信息数据化,形成原始数据,如证件编号、发证日期、有效期、专卖许可单位、准运许可单位等。

2)将原始信息数据采用加密算法进行加密运算,将原始数据变为加密数据。

3)利用二维条码生成软件将加密数据自动转化为二维条码,并通过打印机在打印许可证的同时自动将生成的二维条码打印到许可证上,并对打印的原始数据信息进行自动记录和管理。

3.2 加密二维条码数据识别管理

1)利用二维条码读码器,通过解密运算进行自动阅读、识别与判别真伪。2)利用二维条码读码器,实现数据信息的自动录入,并可对阅读后的数据信息进行自动记录和管理统计,实现办公管理的自动化。

3)通过二维条码,各省市的烟草专卖局可以对其下属的烟草专卖点和准运单位进行统计和专门管理,防止假烟进入烟草市场。

由于加密二维条码的结构直接来自证件的内在信息,因此,加密二维条码一旦形成,证件本身就不能做任何更改,确保证件被涂改之后是无效的。另一方面,由于加密二维条码包含了证件中的大量的内在数据信息,且有专门的读写设备,二维条码中的数据可以自动录入到计算机,因此可充分利用这些条件,对烟草专卖和准运证以及烟草专卖点进行统一数据管理,防止和杜绝假烟进入烟草市场,维护烟草市场的正常秩序。

4 二维条码的应用前景

在一维条码的基础上发展起来的二维条码有着一维条码无法相比的优点,作为一种便携式数据文件,在不断完善的市场经济和快速发展的信息技术的推动下,再加上二维条码其独具的特点,二维条码已开始在国内的很多行业得到应用。

随着科学与信息技术的发展,自动识别技术的种类也越来越多。自动识别技术的发展主要表现在数据质量和录入速度的提高以及消除人为干扰方面,其中表现较为突出的有条码、磁卡、IC卡和射频识别。但二维条码在信息载体的成本、信息量、保密性、抗污染和抗干扰及标准化等方面具有明显的优势,有着良好的推广应用前景。作为信息技术重要组成部分的二维条码,随着信息技术和现代化管理的发展,人们对其认识的提高、理解的加深以及人们对产品和各种证件防伪要求的增加,在我国有着广阔的发展天地。

参考文献

[1]肖军模,等,网络信息安全[M].北京:机械工业出版社,2005,2.

[2]陈向阳,等,计算机网络与通信[M].北京:清华大学出版社,2007,2.

[3]/.