Parallel image encryption algorithm based on discretized
chaotic map
Qing Zhou, Kwok-wo Wong,Xiaofeng Liao,Tao Xiang,Yue Hu
Abstract：Recently, a variety of chaos-based algorithms were proposed for image encryption. Nevertheless, none of them works efficiently in parallel computing environment. In this paper, we propose a framework for parallel image encryption.Based on this framework, a new algorithm is designed using the discretized Kolmogorov flow map. It fulfills all the requirements for a parallel image encryption algorithm. Moreover, it is secure and fast. These properties make it a good choice for image encryption on parallel computing platforms.
1. Introduction
In recent years, there is a rapid growth in the transmission of digital images through computer networks especially the Internet. In most cases, the transmission channels are not secure enough to prevent illegal access by malicious listeners.
Therefore the security and privacy of digital images have become a major concern. Many image encryption
methods have been proposed, of which the chaos-based approach is a promising direction [1–9].
In general, chaotic systems possess several properties which make them essential components in constructing cryptosystems:
(1) Randomness: chaotic systems generate long-period, random-like chaotic sequence in a deterministic way.
(2) Sensitivity: a tiny difference of the initial value or system parameters leads to a vast change of the chaotic sequences.
(3) Simplicity: simple equations can generate complex chaotic sequences.
(4) Ergodicity: a chaotic state variable goes through all states in its phase space, and usually those states are distributed uniformly.
In addition to the above properties, some two-dimensional (2D) chaotic maps are inherent excellent alternatives for permutation of image pixels. Pichler and Scharinger proposed a way to permute the image using Kolmogorov flow map before a diffusion operation [1,2]. Later, Fridrich extended this method to a more generalized way [3]. Chen et al. proposed an image encryption scheme based on 3D cat maps [4]. Lian et al. proposed another algorithm based on standard map [5]. Actually, those algorithms work under the same framework: all the pixels are first permuted with a discretized chaotic map before they are encrypted one by one under the cipher block chain (CBC) mode where the cipher of the
current pixel is influenced by the cipher of previous pixels. The above processes repeat for several rounds and finally the cipher-image is obtained.
This framework is very effective in achieving diffusion throughout the whole image. However, it is not suitable for running in a parallel computing environment. This is because the processing of the current pixel cannot start until the previous one has been encrypted. The computation is still in a sequential mode even if there is more than one processing element (PE). This limitation restricts its application platform since many devices based on FPGA/CPLD or digital circuits can support parallel processing. With the parallel computing technique, the speed of encryption is greatly accelerated.
Another shortcoming of chaos-based image encryption schemes is the relatively slow computing speed. The primary reason is that chaos-based ciphers usually need a large amount of real number multiplication and division operations, which cost vast of computation. The computational efficiency will be increase substantially if the encryption algorithms can be executed on a parallel processing platform.
In this paper, we propose a framework for parallel image encryption. Under such framework, we design a secure and fast algorithm that fulfills all the requirements for parallel image encryption. The rest of the paper is arranged as follows.
Section 2 introduces the parallel operating mode and its requirements. Section 3 presents the definitions and properties of four transformations which form the encryption/decryption algorithm. In Section 4, the processes of encryption, decryption and key scheduling will be described in detail. Experimental results and theoretical analyses are provided in Sections 5 and 6, respectively. Finally, we conclude this paper with a summary.
- Parallel mode
2.1 Parallel mode and its requirements
In parallel computing mode, each PE is responsible for a subset of the image data and possesses its own memory.During the encryption, there may be some communication between PEs (see Fig. 1).
To allow parallel image encryption, the conventional CBC-like mode must be eliminated. However, this will cause a new problem, i.e. how to fulfill the diffusion requirement without such mode. Besides, there arise some additional requirements for parallel image encryption:
1. Computation load balance
The total time of a parallel image encryption scheme is determined by the slowest PE, since other PEs have to wait until such PE finishes its work. Therefore a good parallel computation mode can balance the task distributed to each PE.
2. Communication load balance
There usually exists lots of communication between PEs. For the same reason as of computation load, the communication load should be carefully balanced.
Memory
PE
Memory
PE
Memory
PE
Fig. 1. Parallel computing mode for image encryption.
3. Critical area management
When computing in a parallel mode, many PEs may read or write the same area of memory (i.e. critical area) simultaneously, which often causes unexpected execution of the program. It is thus necessary to use some parallel techniques to manage the critical area.
2.2 A parallel image encryption framework
To fulfill the above requirements, we propose a parallel image encryption framework, which is
剩余内容已隐藏，支付完成后下载完整资料
基于离散混沌映射的图像加密并行算法
摘要：最近，针对图像加密提出了多种基于混沌的算法。然而，它们都无法在并行计算环境中有效工作。在本文中，我们提出了一个并行图像加密的框架。基于此框架内，一个使用离散柯尔莫哥洛夫流映射的新算法被提出。它符合所有并行图像加密算法的要求。此外，它是安全、快速的。这些特性使得它是一个很好的基于并行计算平台上的图像加密选择。
- 介绍
最近几年，通过计算机网络尤其是互联网传输的数字图像有了快速增长。在大多数情况下，传输通道不够安全以防止恶意用户的非法访问。因此，数字图像的安全性和隐私性已成为一个重大问题。许多图像加密方法已经被提出，其中基于混沌的方法是一种很有前途的方向[1-9]。总的来说，混沌系统具有使其成为密码系统建设中重要组成部分的几个属性：
（1）随机性：混沌系统用确定的方法产生长周期、随机的混沌序列。
（2）敏感性：初始值或系统参数的微小差异导致混沌序列的巨大变化。
（3）易用性：简单的公式可以产生复杂的混沌序列。
（4）遍历性：一个混沌状态的变量能够遍历它的相空间里的所有状态，通常这些状态都是均匀分布的。
除了上述性能，有些二维（2D）的混沌映射是图像像素置换天生的优良替代者。Pichler和Scharinger提出一种在扩散操作[1,2]之前使用柯尔莫哥洛夫流映射的图像排列方式。后来，Fridrich将此方法扩展到更广义的方式[3]。陈等人提出基于三维猫映射的图像加密算法[4]l。Lian等人提出基于标准映射的另一种算法[5]。其实，这些算法在相同的框架下工作：所有的像素在用密码分组链接模式（CBC）模式下的加密之前首先被用离散混沌映射置换，当前像素密文由以前的像素密文影响。上述过程重复几轮，最后得到加密图像。
这个框架可以非常有效的实现整个图像的扩散。但是，它是不适合在并行计算环境中运行。这是因为当前像素的处理无法启动直到前一个像素已加密。即使有多个处理元素（PE），这种计算仍然是在一个串行模式下工作。此限制了其应用平台，因为许多基于FPGA / CPLD或者数字电路的设备可以支持并行处理。随着并行计算技术的应用，加密速度可以大大加快。
基于混沌的图像加密方案的另一个缺点是运算速度相对较慢。主要原因是基于混沌的密码通常需要大量的实数乘法和除法运算，计算成本巨大。加密算法在并行处理平台上执行计算效率将大幅提升。
在本文中，我们提出了一个并行图像加密的框架。在这样的框架下，我们设计了一个安全快速算法满足并行图像加密所有要求。本文的其余部分安排如下：第2部分介绍了并行的操作模式和其要求。第3节给出加密解密中四个转换的定义和属性。在第4节，加密、解密的过程和密钥调度会加以详细说明。第5和第6节，提供实验结果与理论分析。最后，我们总结本文 。
2.并行模式
2.1并行模式及其要求
在并行计算模式下，每个PE是负责图像数据的一个子集，并拥有自己的内存。在加密时，可能会有一些PE之间的通信（见图1）。要允许并行图像加密，传统CBC样的模式必须予以打破。然而，这将导致新的问题，即如何实现不在这种模式下的扩散要求。此外，也出现了一些额外针对并行图像加密的要求：
1.计算负载平衡
并行图像加密方案的总时间是由最慢的PE决定，因为其它PE不得不等待直至这个PE完成其工作。因此，良好的并行计算模式可以平衡分配给每个PE的任务。
2.通信负载平衡
通常存在有大量的PE之间的通信。基于和计算负载同样的原因，通信负载应认真平衡。
3.临界区管理
在并行模式计算时，许多的PE可以同时读取或写入相同的内存区域（即临界区），
这往往会导致意想不到的执行程序。因此，有必要在关键区域使用一些并行技术管理。
2.2并行图像的加密框架
为了满足上述要求，我们提出了一个并行图像加密的框架，这是一个四个步骤的过程：
步骤1：整个图像被划分成若干块。
步骤2：每个PE负责确定数量块。一个区域内的像素可以充分使用有效的混乱和扩散进行操作加密。
步骤3：通过PE之间的通信交换加密数据块从块到更大范围的扩散。
步骤4：转到第2步，直到加密图像达到所需的安全级别。
在第2步，已经实现扩散，但只有一个块的一个小部分。但在第3步的帮助下，这样的扩散效应被扩大。请注意，从加密的角度，在步骤3中的数据交换本质上是一个置换。经过多次迭代步骤2和3，扩散效应蔓延到整个图像。这意味着在一个普通的图像像素的微小变化会波及到了大量的加密图像的像素。为了使框架足够安全，两个要求必须被满足：
1.第2步中的加密算法混乱和扩散的特点应该是足够安全的，而且对明文和密钥敏感。
2.在步骤3中的置换在几个回合变化中必须从局部蔓延到所有部分。
结合不同的加密元素可以满足第一个要求，如S-盒，Feistel 结构，矩阵乘法和混沌映射等，或者我们可以只使用一个传统的加密标准，如AES或IDEA。然而，第二个是由于这一框架而产生的一个新课题。此外，这样的置换应有助于实现2.1节中提出的三个附加目标。因此，置换操作是本文的重点之一，应认真研究。
这种并行图像加密框架下，我们提出了一种新的算法，这是基于四个基本的转换。因此，我们将描述我们的算法之前，先介绍这些转换。
3.转换
3.1 A-转换
在A转换中，A代表加，能被形式化的定义如下：
a b=c (1)
加法被定义为按位与操作
转换A有三个基本性质：
(2.1)a a=0
(2.2)a b=b a (2)
(2.3)(a b) c=a (b c)
3.2 M-转换
在M转换中，M代表混合数据
首先，我们介绍和转换：
sum：
定义sum（I）： (3)
sum（I）=
然后给出M转换的定义
M：
让M（I）=C 让I= C= (4)
容易证明M转换有如下性质：
（5.1）M（M（I））=I (5)
（5.2）M（I J）=M（I） M（J）
（5.3）M（kj）=kM（I），where kI=，k
需要指出的是，从所有从（3）—（5）的加法运算其实是A转换。
3.3 S-转换
在S-变换中，“S”代表S盒置换。有很多方法来构造S盒，其中混沌的做法是一个很好的选择。例如，唐等人提出了一个基于离散逻辑映射和Baker映射[10]的设计S-盒的方法。之后，陈等人提出另一种方法来构造S盒，具有更好的性能[11]。该过程描述如下：
步骤1：选择一个Chebyshev映射的初始值，然后迭代映射生成初始的S-盒表。
步骤2：把二维表加载到三维表上。
步骤3：多次应用离散化的三维Baker映射使表格混乱。最后，把三维表转换成二维，以获得所需的S-盒。
实验结果表明，由此产生的S-盒是加密应用程序的理想选择。该方法也被称为“动态”的，当Chebyshev映射的初始值被改变时得到不同的S-盒。然而，为了简化和性能，我们使用一个固定的S-盒，即在[11]给出的例子见表1。
3.4 K-转换
在K-转换中，“K”代表柯尔莫哥洛夫流，通常被称为广义Baker映射[3]。图像加密应用程序的Kolmogorov流由Picher和Scharinger首次提出 [1,2]。
离散形的K-流如（6）：
（x，y）=（（x-） （y mod ）， （y div ）） （6）
其中=（n1，n2，hellip;..nk），是一个正整数=N，划分把s和N分开，=一个垂直的s的范围：
=
需要注意的是（6）可以用图2中的几何变换来解释。N*N图像可以划分为高N和宽度Ns的垂直矩形。然后又进一步分为箱子每一个垂直的矩高度Ps宽度Ns。 K -映射后，从同一个盒子的像素实际上是映射到一个单行的。
4．MASK-一个并行的图像加密体系
4.1加密方案的概要
假设的N·N图像是由n个 PE同时加密的，我们描述并行加密方案如下：
1.每个PE负责图像中像素的一些固定行。
2.每行的像素分别使用M，A，S进行加密。
3.根据置位转型K进一步扩散的所有像素。
4.转到第二步进行另一轮的加密，直到密文足够安全。
如上所述，在第3步中的置换是非常重要的，因为它有助于满足安全性和速度要求。因此，置换的映射和它的参数，一定要慎重选择。在我们的算法中，是常数向量其长度为q，其中q = N / n。向量的每个元素都等于n：
=（n，n，hellip;.n）1q(7)
每个PE负责q个连续的行，或者更具体地说，第i个PE行负责从（i-1）*q 到i*q-1
的行。该算法可以实现并行加密的所有要求，分析如下。
1.整个图像的扩散效应
假设在第2步的操作有足够的安全。第2步后，明文像素的微小变化会扩散到整行的N个像素。如果我们根据Eq（7）选用，很容易证明，这N个加密的像素会在第3步K变换中会置换到不同的q行。同样，另一轮加密过后，改变会扩散到q行，第3轮后，整个加密图像已经改变。因此，在我们的方案中，任何单个像素的最小变化会在3轮后扩散到整个图像。
2.通讯负载平衡
如果参数（6）中的参数（7）那样选择，很容易证明，两个PE之间的数据交换是不变的，即等于图像的像素总数的1/q2。对于每个PE，这个数量变为（q-1）/ 。因此，在我们的方案中，每个PE的通信负载是等效的，并没有任何通讯负载不平衡。
3.平衡负载的计算
每个PE将要加密的数据都是像素q行，因此计算负载平衡自然实现。
4.临界区管理
在我们的体制中，不会发生两个PE读取或写入到相同的内存。因此，我们不必像其他并行计算体制经常做的一样需要施加任何关键领域的管理技术。
上述讨论表明，该方案能实现并行图像加密的所有要求，这主要归因于混沌柯尔莫哥洛夫映射和其参数的选择。
4.2加密
密文经过数轮加密才能产生。然而，在第一轮中，图像预先经过K置换处理。然后在每一轮中，分别进行M，A，S，K的变换。最后一轮与前面不同之处在于S-变换故意遗漏。M，A，S变换通过PE操作一行中的每个像素，而这K操作对整个图像的运作必然涉及到PE之间的通信。加密过程是由伪代码在图3中列出所描述的。
4.3轮密钥生成
在四个置换中，只有置换A需要一个轮密钥。对于8位灰度图像的N*N像素，一个包含N个字节的轮密钥应在每一轮为置换A产生。
一般来说，轮密钥应该是伪随机和敏感的。从这个角度来看，一个混沌映射是一个很好的选择。在我们的体系中，我们使用斜帐篷映射生成所需的轮密钥。
= (8)
混沌序列由系统参数和混沌映射的初始状态确定，它们是0和1之间的实数。虽然混沌映射方程很简单，它生成的伪随机序列对系统参数和初始状态敏感。这个属性使得映射是密钥生成的理想选择。
在数字计算机实施时，映射状态存储为一个浮点数。第一个轮状态的8位被提取作为一个字节的轮密钥。因此，我们每一轮需要N次迭代斜帐篷映射。
4.4解码
一般情况下，解密程序是由一个相反的顺序执行加密转换组成。此性质也在我
们的体系中。然而，经过精心的设计，我们体系中解密过程是相同的，而不是反转，转换为密码。这个令人印象深刻的特征属性归功于以下变换的两个属性：
（1）置换-S和置换 - K可交换。置换-S只替换每个像素的值而独立于它的位置。另一方面，置换 - K只改变一个像素的位置其值不变。因此，两者之间的转换关系可表示为（9）：
K（S（I））=S（K（I）） (9)
（2）根据（5）置换-M是一个线性操作。此外，（5.2）中定义的加实际上是置换-A。因此， 两者之间的转换关系可表示为（10）：
M（A（I，J））=A（M（I），M（J）） (10)
总之，无论是置换S和K时，还是置换M和A，可以互换计算顺序对最终结果没有影响。表2说明了这两个属性如何影响置换的顺序，应用简单的2轮加密例子加以证明。
很容易观察
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[19738]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
课题毕业论文、文献综述、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
