安企神电脑监控软件 在线试用
扫码咨询客服
安企神电脑监控软件、局域网监控软件
首页
功能介绍
产品简介
下载中心
帮助中心
客户列表
关于安企神

写给大家看的RSA加密算法

更新时间:2022-10-28 15:46:30


本文简介:前段时间看的《王牌特工》帅气的科林叔一把绅士伞在手,天下我有的气势征服了所有观众,凡是特工就没有不和加密解密打交道的,我们经常看到侦探电影的桥段,勇敢又机智的主角,拿着一长串毫无意义的数字苦恼,忽然灵光一闪,翻出一本厚书,将第一个数字对应页码数,第二个数字对应行数,第三个数字对应那一行的某个词。数字变成了一串非常有意义的话:Eat the beancurd with the peanut. Tas

写给大家看的RSA加密算法

前段时间看的《王牌特工》帅气的科林叔一把绅士伞在手,天下我有的气势征服了所有观众,凡是特工就没有不和加密解密打交道的,我们经常看到侦探电影的桥段,勇敢又机智的主角,拿着一长串毫无意义的数字苦恼,忽然灵光一闪,翻出一本厚书,将第一个数字对应页码数,第二个数字对应行数,第三个数字对应那一行的某个词。数字变成了一串非常有意义的话:

Eat the beancurd with the peanut. Taste like the ham.

主角喜极而泣……

这种加密方法是将原来的某种信息按照某个规律打乱。某种打乱的方式就叫做密钥(cipher code)。发出信息的人根据密钥来给信息加密,而接收信息的人利用相同的密钥,来给信息解密。就好像一个带锁的盒子。发送信息的人将信息放到盒子里,用钥匙锁上。而接受信息的人则用相同的钥匙打开。加密和解密用的是同一个密钥,这种加密称为对称加密(symmetric encryption)。

1

如果一对一的话,那么两人需要交换一个密钥。一对多的话,比如总部和多个特工的通信,依然可以使用同一套密钥。但这种情况下,对手偷到一个密钥的话,就知道所有交流的信息了。二战中盟军的情报战成果,很多都来自于破获这种对称加密的密钥。

1

二战中德军的传奇加密机:Enigma

为了更安全,总部需要给每个特工都设计一个不同的密钥。如果是FBI这样庞大的机构,恐怕很难维护这么多的密钥。在现代社会,每个人的信用卡信息都需要加密。一一设计密钥的话,银行怕是要跪了。

 

对称加密的薄弱之处在于给了太多人的钥匙。如果只给特工锁,而总部保有钥匙,那就容易了。特工将信息用锁锁到盒子里,谁也打不开,除非到总部用唯一的一把钥匙打开。只是这样的话,特工每次出门都要带上许多锁,太容易被识破身份了。总部老大想了想,干脆就把造锁的技术公开了。特工,或者任何其它人,可以就地取材,按照图纸造锁,但无法根据图纸造出钥匙。钥匙只有总部的那一把。

1

上面的关键是锁和钥匙工艺不同。知道了锁,并不能知道钥匙。这样,银行可以将“造锁”的方法公布给所有用户。每个用户可以用锁来加密自己的信用卡信息。即使被别人窃听到,也不用担心:只有银行才有钥匙呢!这样一种加密算法叫做非对称加密(asymmetric encryption)。非对称加密的经典算法是RSA算法。它来自于数论与计算机计数的奇妙结合。

为了了解RSA加密,请听一个卧底的自白:

RSA加密

我是潜伏在龙凤大酒楼的卧底。想让下面信息以加密的方式发送到总部:

A CHEF HIDE A BED

厨子藏起来了一张床!这是如此的重要,需要立即通知总部。千万重要的是,不能让反革命的厨子知道。

第一步是转码,也就是将英文转换成某个对应的数字。这个对应很容易建立,比如:

A B C D E F G H I
1 2 3 4 5 6 7 8 9

将上面的信息转码,获得下面的数字序列:

A CHEF HIDE A BED

1 3856 8945 1 254

这串数字完全没有什么秘密可言。厨子发现了这串数字之后,很容易根据数字顺序,对应字母表猜出来。

为了和狡猾的厨子斗智斗勇,我们需要对这串数字进一步加密。使用总部发给我们的锁,两个数字:3和10。我们分为两步处理。

第一步是求乘方。第一个数字是3,也就是说,总部指示我们,求上面数字串的3次方:

原字符串: 1   3   8   5   6   8   9   4   5   1   2   5   4

三次乘方: 1  27 512 125 216 512 729  64 125   1   8 125  64

第二步是求余数。第二个上锁的数字是10,将上面每个三次乘方除以10,获得其余数:

余数: 1 7 2 5 6 2 9 4 5 1 8 5 4

将这串数字发回总部。中途被厨子偷看到,但一时不能了解其中的意思。如果还是像刚才一样对应字母表的话,信息是:

AGBEFBIDEAHED

这串字母完全不包含正常的单词。

信息到了总部。总部开始用神奇的钥匙来解读。这个钥匙是3。(偷偷告诉你的,别告诉厨子。)

(这里钥匙不小心和之前锁中的一个数字相同。这只是巧合。)

解锁过程也是两步。第一步求钥匙次的乘方,即3次方。第二步求它们除以10(锁之一)的余数。

加密信息:1   7   2   5   6   2   9   4   5   1   8   5   4

三次乘方:1 343   8 125 216   8 729  64 125   1 512 125  64 (这里用的是钥匙的“3”)

除十得余:1   3   8   5   6   8   9   4   5   1   2   5   4

正是我们发送的信息。对应字母表,总部可以立即知道原来的信息。

总结

正如我在“数学与编程”中提到的,数学可以是程序员军火库中有力的武器。加密、解密这一事关IT安全的大课题,却和数论这一纯粹数学学科发生奇妙的关系。RSA算法的数学基础在于欧拉定理。这一诞生了几百年没有什么实用性的数学理论,却在网络时代,找到自己的栖身之处。

加密算法有很多,这次我们只讲RSA算法。公开的加密方式,私有的解密方式。RSA安全的关键在于很难对一个大的整数进行因子分解。相信这次你应该对于RSA加密不再恐惧了吧。

立即下载试用

图像加密算法之Fibonacci双置乱

大家都知道,像置乱是实现图像加密的重要手段之一,其最终目的是改变图像像素的位置关系或者灰度值信息,改变图像的统计信息,从而达到图像加密的目的。为提升图像置乱效果和置乱性能,从均匀分块的角度出发,提出了一种改进的Fibonacci双置乱图像加密算法。

一、Fibonacci加密算法

1、Fibonacci像素位置变换

Fibonacci的变换矩阵如式(1)、式(2)所示。

图像像素的位置矩阵表示为p(x,y)H,二维Fibonacci位置变换表达式为:

对图像做n次Fibonacci位置变换的表达式为:

x,y,x',y'∈{O,1,…,N},N为数字图像矩阵的阶数;(x,y)和(x',y')分别是原图像和置乱后图像像素的位置。

2、Fibonacci像素值变换

无论位置置乱还是像素值置乱,其二维Flbonaccl变换矩阵相同,都如式(1)、式(2)所示。与位置置乱不同,h表示任意像素值横纵坐标的十六进制,不再是像素的位置坐标。对图像像素值h变换一次的表示形式如下:

则对图像像素值h变换n次的表示形式为:

式中,h=(h1,h2)H,hi,hi'∈{1,2,…,n},i=l,2,则h'(hi,hi')H是对每个像素值h置乱后对应的像素值。

3、Fibonacci双置乱

Fibonacdi双置乱算法的主要思想是利用图像矩阵左乘二维Fibonacdi变换矩阵,先改变图像像素位置,再改变像素的灰度值,算法分两步进行;

(1)对图像的像素进行kl次位置置乱,削弱图像的空间相关性。

(2)对图像的像素进行k2次灰度值置乱,削弱图像的色彩相关性。最终得到随机生成的密钥序列,具体的置乱流程如图1所示。

二、均匀分块算法

1、图像均匀分块原理

图像能够传达信息是因为图像的像素值之间具有差异性,图像位置置乱的目的是分散。相邻像素点一,从而最大程度地破坏像素之间的相关性.从信息论角度,图像置乱的目的是降低图像相邻像素的相关性,使图像像素由最大确定性变换为不确定性的过程,即增加图像信息量的过程。首先提出图像位置熵的定义:

式中,B为图像分块区域个数;Hk(P)为第正个分块区域的信息熵,即第k个分块区域平均位置信息量,可表示如下:

式中,P(i,j)为原始图像坐标为(i,j)的像素在置乱后图像第k个分块区域出现的概率.刚当P(i,j)等概率时熵函数Hk(P)最大,从而位置熵H(R)最大。

理想的置乱状态是置乱图像中任意分块区域内的点来自原始图像各个位置的概率都相等,或者说原始图像同一分块区域内的点分布到置乱图像不同分块区域的概率相等,则置乱后图像信源的平均信息量最大,置乱效果最好。为达到理想的置乱效果,提出如下均匀置乱方法:若原始图像中每块含有nXn个点。如果这些点分别出现在置乱后图像的n×n个图像块中,不管这些点在置乱后图像各块中出现的顺序如何,只要保证每块中各含有一个点,就称为均匀置乱。

2、图像的块置乱

假设图像的尺寸为MXN,以f(i,j)(1≤i≤M,1≤j≤N)为中心的m×n(O≤m≤M,0≤n≤N)个相邻像素组成的一个邻域,称为图像块。

(1)先将图像做分块处理,通常正方块在图像加密的研究中最有代表意义,图像分块需做如下约束:

①图像行数等于列数,而且是2的指数;

②图像平均分成若干块,每块的行数都等于列数。具体的分块过程如下:

将原始图像分成M1块,每块含有N1个点,置乱后图像分成M2块,每块含有N2个点,那么实现原始图像各块中像素点间的距离由“最近”到“最远”,如图2所示,要保证该块中所有像素点被分到置乱后图像的不同块中,则M2≥N1;同理,实现原始图像各块中像素点间的距离由“最远”到“最近”,就必须保证在原始图像所有块中各取的一点,都能分到置乱后图像的同一块中,则N2≥M1。因为M2≥N1,N2≥M1,则M2,N2≥Ni N2≥M1, Ni,已知M2N2=M1N1;那么M2=N,M=N2。

令原图像由16×16个像素点组成,每块中有2×2个点,共分成8×8块,置乱后的图像为每块中有8×8个像素点,共分成2×2块,如图2所示。

(2)分别将置乱后的每个图像块按式(4)做Fibonacci位置变换,图像的加密流程如图3所示。其中Orilmage是原始图像,Scrlmage是加密图像。

图像的懈密是加密的逆过程。即利用已知密钥,首先将加密图像做Fibonacci反变换,对图像的像索值置乱进行恢复,然后按照加密时块置乱的规律采用均匀分块算法,最后对图像块做Fibonacci反变换,对图像块的像东位置置乱进行恢复,就能将原始图像还原。

三、实验效果与分析

1、相邻像素相关性分析

图像的本质特征决定了图像中栩邻像素间具有很大的相关性,利用该性质的统计攻击方法来分析图像的加密算法就成为可能,因此用相关系数来衡量加密算法破坏相邻像素相关性的能力。首先,从图像中随机选取1000对相邻像素点(水平、垂直和对角),然后利用以下公式进行计算。

式中,x和y分别表示相邻两个像索的像索值,E(.)、D(.)和Cov(.)分别是期望、方差和协方差,r是相邻两像素的相关系数,其值接近1的程度越高,相邻像索的相关性越高。将Lenna图像分别采用传统的整体Fibonacci置乱算法与本文算法进行相邻像素相关性对比实验,比较图像在3个方向的相邻像素相关性。通过表1的计算结果可见,原始图像的相邻像素是高度相关的,相关系数接近于1,密图的像素相关性接近于O,而且利用本文算法能更大程度地降低相邻像素的相关性,几乎达到了O相关。可见采用改进的双置乱加密算法明显优于传统的Fibonacci置乱算法。

2、置乱效果比较

图像置乱包括位置置乱和像素值置乱,置乱的最终目的是实现最大程度的混乱和扩散,对位置置乱而言,如果原始图像任意小的部分都能在加密之后的图像中呈均匀分布,那么可将其看作理想状态,对像素值置乱而言,如果加密之后的像索值能住(0~255)范围内呈均匀分布,即将灰度直方图的均匀分布看作理想状态。从图4可见,传统的置乱算法多数是对图像整体进行位置置乱,加密多次才能达到理想效果,而且单纯的位置置乱即使迭代多次,其灰度直方图也达术到均匀分布的状态,没有削弱图像像素的相关性,然而采用双置乱算法可以在较少的置乱次数下达到混乱和扩散的理想效果,有效削弱了图像像素的相关性。

传统分块方法分3步进行:

①将图像进行分块,假设图像大小为256X256,分块数为32X32,则计算每个图像块中像素点的个数为(256×256)÷(32X32)=8X8=64。

②对含有64个像素点的块进行位置置乱。

③采用幻方变换对图像整体进行加密。

第一行和第二行分别是采用传统分块算法和本文算法由不同分块数目获得的加密效果,如图5所示。

从图5可见,传统的分块方法具有一定的置乱效果,但随着分块数目的增加,原始图像信息逐渐从加密图像中显现出来,所以传统的分块算法有一定的局限性;而改进的分块方法分块数目越多,置乱效果越好,这是因为改进的方法采用均匀分块思想能够将图像像素均匀打乱,所以改进分块方法在图像加密中更具有实际的应用价值。

3、抗算切实验

衡量图像加密性能一般采用误码率BER、归一化相关系数NC和信噪比SNR 3个指标,它们的定义如下:

式中,M和N分别为错误比特数和总比特数,w(i,j)和W1(i,j)分别为原始图像和对加密图像进行裁剪后恢复图像的数据量;A和A’分别是原始图像和加密图像的方差。表2给出图像对随机裁剪攻击的鲁棒性实验结果。

首先采用本文算法对Lena图像进行加密处理,然后利用Adobe photoshop软件对加密图像按图6的方案裁剪,图6(d)一(f)分别是对图6(a)一(c)裁剪攻击恢复的效果图。

由裁剪攻击实验得知,对裁剪后的图像进行恢复会存在一定程度的失真,但是要辨认图像所传达的信息并不困难,通过该实验发现,加密图像恢复的效果与裁剪的位置几乎无关,主要因为改进的双置乱算法采用了均匀分块和图像块置乱的思想,使得每个图像块的像素都均匀分布到其他各个图像块,即“广泛分布”,而非“集中分布”,从本质上削弱了图像内部相邻像素的相关性,所以该算法能有效地抵抗裁剪攻击,一定程度的裁剪对图像的恢复影响不大。

4、抗噪声实验

图像数据一般用于网络传输,因此不可避免地会受到一些噪声或信道干扰。借此,采用实验验证本文算法抵御噪声攻击的能力是必要的,根据式(13) -式(15)计算加密图像在不同的Gauss噪声攻击下的性能,如表3所列。

在加密图像中加入不同程度的高斯白噪声,其中参数m和σ分别代表均值和均方差,加入均值m,均方差σ不同的高斯噪声,图7(d)一(f)分别是利用解密算法对图7(a)-(c)的恢复效果图。

通过采用不同参数对密图进行噪卢攻击的实验可以看出,当图像受到一定程度的噪声污染时基本能恢复原图像,总体上并不会影响图像所展现的内容,证明了本文算法在一定程度上抵御噪声的性能较强。

小知识之Fibonacci

斐波那契堆(Fibonacci heap)是计算机科学中最小堆有序树的集合。它和二项式堆有类似的性质,可用于实现合并优先队列。

本文为收集整理,文章部分观点不代表本站观点,如有侵权或其它问题请反馈客服。https://www.wgj7.com/cjwt/16479.html