12.5.1 以排序法为基础的混沌置乱（1）
排序手段可以获得量化数值序列的唯一排列，也就是说，当有限实数集合中的元素稳定后，排序结果具有唯一性。常见的排序方法包括冒泡排序法、选择排序法和快速排序法等。因此可以考虑通过混沌系统生成数值序列后，对序列进行排序，进而得到矩阵变换关系，并由生成的矩阵变换关系对图像进行扰乱。设数字图像用f表示，其宽度为W，其高度为H（均以像素计），下面给出以排序法为基础的混沌置乱算法的具体步骤。
① 选择一个混沌映射（以一维Logistic映射为例），利用初始参数来产生混沌序列。同时再选择一个长度为k的整数序列δ = (n1, n2, …, nk )，0 < ni < n，其中n是图像行的大小，即n = W。可以把这些参数作为密钥。
② 利用混沌映射产生一个混沌序列{x1, x2,…, xn}。将实值序列集合{x1, x2,…, xn}中的n个值由小到大排序，形成有序序列{x′1, x′2,…, x′n}。确定混沌实值序列{x1, x2,…, xn}中的每个xi在有序序列{x′1, x′2,…, x′n}中的位置编号，形成置换地址集合{t1, t2,…, tn}，其中ti为集合{1, 2,…, n}中的一个，按置换地址集合{t1, t2,…, tn}对图像的第1行像素进行置换。
③ 更换混沌映射的初始条件以形成新的混沌序列。可以使用整数序列中的ni作为一个影响参数，通过这个新的参数从上一个混沌序列中选出当前新序列的起始迭代点，并使用新产生的混沌序列来构造置换矩阵。待得到置换矩阵后对新的一行进行处理，即对第2行到第H行重复步骤2，直到将图像的所有行进行置乱完毕。如果出现ni=nk的情况，则重新从n1开始循环使用δ。
④ 对图像的列做相似的变换。
以上介绍的是一种设法引入混沌后，构造出的一种以排序作为核心思想的图像置乱算法。以此为出发点还可以继续优化、改造出其他加密算法。
下面编程来实现这种加密算法。以MagicHouse为基础进行开发。打开MagicHouse项目，并在其中添加一个对话框，如图12-14所示，该对话框实现了上述混沌置乱加密算法。交互界面上需要用户输入首次混沌序列生成时的参数。输入序列长度后，系统可以自动生成随机整数序列。迭代次数控制了对图像进行加密的轮数。
为上述对话框创建一个类CDlgChaosE1，下面列出DlgChaosE1.cpp文件的核心代码清单，请读者注意这里略去了部分非关键代码。该文件的完整源代码及项目中其他文件的代码清单请读者参看随书光盘。
- #include "stdafx.h"
- #include "MagicHouse.h"
- #include "DlgChaosE1.h"
-
- //CDlgChaosE1 对话框
-
- IMPLEMENT_DYNAMIC(CDlgChaosE1, CDialog)
-
- CDlgChaosE1::CDlgChaosE1(CWnd* pParent, BYTE* temp_imageBuffer,
- int Ximage, int Yimage): CDialog(CDlgChaosE1::IDD, pParent)
- {
- //{{AFX_DATA_INIT(CDlgKeySetting)
- m_key_u = 0.0;
- m_key_x0 = 0.0;
- m_key_len = 0;
- m_times = 0;
- m_KeyListToString = _T("");
- image_temp = temp_imageBuffer;
- //}}AFX_DATA_INIT
- X_image = Ximage;
- Y_image = Yimage;
- }
-
- //此处省略了部分系统自动生成的代码
-
- void CDlgChaosE1::swapInt(int& x, int& y) {
- int t;
- t = x;
- x = y;
- y = t;
- }
-
- int CDlgChaosE1::partition(double* x,int* t,int low, int high)
- {
- double key = x[low];
- while(low < high) {
- while(low < high && x[t[high]] >= key) high--;
- swapInt(t[low], t[high]);
- while(low < high && x[t[low]] <= key) low++;
- swapInt(t[low], t[high]);
- }
- return low;
- }
-
- void CDlgChaosE1::getTSort(double* x,int* t, int low, int high)
- {
- if(low < high) {
- int pivot = partition(x, t, low, high);
- getTSort(x, t, low, pivot - 1);
- getTSort(x, t, pivot + 1, high);
- }
- }
-
- //CDlgChaosE1 消息处理程序
- void CDlgChaosE1::EncryptionBasedChaos()
- {
- int * t = NULL;
- double * x = NULL;
-
- for(int times=0; times<m_times; times++)
- {
- // First Row
- t = new int[X_image];
- x = new double[X_image];
-
- x[0] = m_key_x0;
- for (int p=0; p<Y_image; p++)
- {
- for (int i=1; i<X_image; i++)
- {
- x[i] = m_key_u * x[i-1] * (1 - x[i-1]);
- t[i] = i;
- }
-
- t[0] = 0;
- getTSort(x,t,0,X_image-1);
- x[0] = x[t_keyList1[p%m_key_len]];
- for (int j=0; j<X_image; j++)
- {
- swap(image_temp[j*4+p*X_image*4],
- image_temp[t[j]*4+p*X_image*4]);
- swap(image_temp[j*4+p*X_image*4+1],
- image_temp[t[j]*4+p*X_image*4+1]);
- swap(image_temp[j*4+p*X_image*4+2],
- image_temp[t[j]*4+p*X_image*4+2]);
- swap(image_temp[j*4+p*X_image*4+3],
- image_temp[t[j]*4+p*X_image*4+3]);
- }
- }
-
- // Then Column
- delete[] t;
- delete[] x;
-
- t = new int[Y_image];
- x = new double[Y_image];
-
- x[0] = m_key_x0;
- for (int p=0; p<X_image; p++) {
- for (int i=1; i<Y_image; i++) {
- x[i] = m_key_u * x[i-1] * (1 - x[i-1]);
- t[i]= i;
- }
-
- t[0] = 0;
- getTSort(x,t,0,Y_image-1);
- x[0] = x[t_keyList2[p%m_key_len]];
- for (int j=0; j<Y_image; j++) {
- swap(image_temp[j*X_image*4 + p*4],
- image_temp[t[j]*X_image*4 + p*4]);
- swap(image_temp[j*X_image*4 + p*4+1],
- image_temp[t[j]*X_image*4 + p*4+1]);
- swap(image_temp[j*X_image*4 + p*4+2],
- image_temp[t[j]*X_image*4 + p*4+2]);
- swap(image_temp[j*X_image*4 + p*4+3],
- image_temp[t[j]*X_image*4 + p*4+3]);
- }
- }
- delete[] t;
- delete[] x;
- }
- }
-
- void CDlgChaosE1::OnBnClickedOk()
- {
- UpdateData(TRUE);
- if(m_KeyListToString.IsEmpty())
- {
- MessageBox(L"请设置密钥!",L"Magic House", MB_ICONWARNING);
- return;
- }
-
- int loc=0;
- int loc_last = 0;
- t_keyList1.clear();
- t_keyList2.clear();
-
- int locKey2 = m_KeyListToString.Find(L"Key2",0);
- for (loc=m_KeyListToString.Find(L" ",0); loc<locKey2;)
- {
- int next = m_KeyListToString.Find(L" ",loc+1);
- int keys = _ttoi(m_KeyListToString.Mid(loc+1,next-loc-1));//
- t_keyList1.push_back(keys);
- loc = next;
- }
-
- for (loc=m_KeyListToString.Find(L" ",locKey2); loc>=0;)
- {
- int next = m_KeyListToString.Find(L" ",loc+1);
- int keys = _ttoi(m_KeyListToString.Mid(loc+1,next-loc-1));
- t_keyList2.push_back(keys);
- locloc_last = loc;
- loc = next;
- }
-
- t_keyList2.pop_back();
- int keys = _ttoi(m_KeyListToString.Mid(loc_last+1,
- m_KeyListToString.GetLength()));
- t_keyList2.push_back(keys);
- EncryptionBasedChaos();
-
- OnOK();
- }
-
- void CDlgChaosE1::OnBnClickedButtonP()
- {
- UpdateData(TRUE);
-
- t_keyList1.clear();
- t_keyList2.clear();
-
- int last_element = 0;
- m_KeyListToString = "Key1:";
- if (X_image != 0 && Y_image != 0)
- {
- for (int i=0; i<m_key_len; i++)
- {
- CString temp;
- temp.Format(L"%d",abs(rand()%X_image));
- m_KeyListToString += L" "+ temp;
- }
-
- m_KeyListToString += L"\r\nKey2:" ;
- for (int i=0; i<m_key_len; i++)
- {
- CString temp;
- temp.Format(L"%d", abs(rand()%Y_image));
- m_KeyListToString += L" "+ temp;
- }
- }
- UpdateData(FALSE);
- }
-
- BOOL CDlgChaosE1::OnInitDialog()
- {
- CDialog::OnInitDialog();
-
- m_KeyListToString = "";
- m_key_len = 128;
- m_key_u = 3.7;
- m_key_x0= 0.7;
- m_times = 3;
- m_SpinKey3.SetRange(1,256);
- m_SpinKey4.SetRange(1,10);
-
- UpdateData(false);
- return TRUE;
- }