栅栏密码

条形栅栏密码

甚么是条形密码?看完加密方法就有直观的认识了

加密算法

这里将栅栏横着放用行line表示,有0到h-1共h行对应h个栅栏

设要加密的文本text,其字符下标从0开始

然后text[0]分配给0号栅栏

text[1]分配给1号栅栏

…

text[n]分配给n号栅栏

text[h-1]分配给h-1号栅栏

text[h]分配给1号栅栏

text[h+1]分配给2号栅栏

以此类推

也就是说已知当前行(栅栏号)为n则下一个栅栏应该是(n+1)%h

最终text的字符被这样轮流分配完毕,然后将各行按顺序合并得到加密密码

密码=line[0]+line[1]+line[2]+...+line[h-1]

算法设计:

bool isSpace(const char &c) {//忽略所有空格回车换行if (c == ' ' || c == '\n' || c == '\r')return true;return false;
}//栅栏密码算法
string fence_encrypt(const string &text, const int &cnt_fence) {//这里cnt_fence栅栏数就是前文的hstring fences[cnt_fence];int length = text.length();int now = 0;for (auto c : text) {if (isSpace(c))continue;fences[now] += c;//c放入当前栅栏now = (now + 1) % cnt_fence;//now指向下一个栅栏的位置}string encrypted;for (int i = 0; i < cnt_fence; i++) {encrypted += fences[i];}return encrypted;
}

解密算法

那拿来的放回哪里去,实际上解密算法和加密算法是完全相同的

string fence_decrypt(const string &encrypted, const int &cnt_fence) {string fences[cnt_fence];int length = encrypted.length();int now = 0;for (auto c : encrypted) {fences[now] += c;now = (now + 1) % cnt_fence;}string text;for (int i = 0; i < cnt_fence; i++) {text += fences[i];}return text;
}

W形栅栏密码

啥叫WWW加密呢?

区别于条形栅栏加密

条形栅栏加密:

将123456789A进行深度为3(栅栏数为3)的条形栅栏加密得到

line[0]=	1	4	7	A
line[1]=	2	5	8
line[2]=	3	6	9

密文为第0行+第1行+第2行=147A258369

注意实际编程的时候下标从0开始

考虑用W形将明文123456789A加密,深度为3

line[0]=	--1---5---9--
line[1]=	---2-4-6-8-A-
line[2]=	----3---7----

密文为第0行+第1行+第2行=1592468A37

也就是说,方向是这样的:

是个W形状,因此叫做WWW加密算法

WWW加密算法设计

我们需要加密的明文为text,text[0]表示明文的第0个字符

当深度为3的时候,

text[0]放在第0行

text[1]放在第1行

text[2]放在第2行

text[3]放在第1行

…

即text的字符会依次放在第0,1,2,1,0,1,2,1,0…行

规定一个方向指示director,下(+1),上(-1),表示下一个字符应该放在当前字符归属行的上一行还是下一行

这个方向只能在达到最高处(第0行)或者达到最低处(第h-1行)转向,在中间的行(1到h-2行)只能遵守规定号的方向跳转,

这个过程神似穿针引线,从左上缝补到右下,然后到右上然后右下…

具体算法如下:

	int now=0;//当前行指针int director;//方向标识for (auto c : text) {if (now == 0)director = 1;//如果当前位置now在最高行则规定方向=1表示下一行应往低处(0->h-1方向)跳转else if (now == h - 1)director = -1;//如果当前位置now在最低行则规定方向=-1表示下一行应往高处(h-1->0)方向跳转//注意这里没有[2,h-2]这些行的条件判断,意味着这些行不会修改director方向,只会遵守方向lines[now] += c;//字符c加入当前行now = now + director;//根据director指示跳转到下一行}

完整代码:

string WWW_encrypt(const string &text, const int &h) {string lines[h];int length = text.length();int now = 0;int director;for (auto c : text) {if (now == 0)director = 1;else if (now == h - 1)director = -1;lines[now] += c;now = now + director;}string encrypted;for (int i = 0; i < h; i++) {//按照从0到h-1的顺序将各行拼接起来encrypted += lines[i];}return encrypted;
}

WWW解密算法推导

还是观察明文123456789A加密,深度为3的例子

line[0]=	--1---5---9--
line[1]=	---2-4-6-8-A-
line[2]=	----3---7----

密文为第0行+第1行+第2行=1592468A37

发现我们只需要还原出这三行的内容来然后借用刚才加密的思想,使用方向指示就可以还原出未加密的文本

关键在于怎么确定这几行每行的内容是啥

密文的前三个159归属第0行

然后2468A五个归属于第1行,

然后37两个归属于第2行,

貌似没有规律,不能确定哪几个归属于哪一行

但是可以确定的是,归属于同一行的字符一定挨着,并且最开始一定是归属于第一行的,然后是归属于第二行的,以此类推

确定字符对各行的分配规则cnt数组

定义"周期"

我们把红框称为"上周期",其中不含最低行(第h-1行)的字符
我们把黑框称为"下周期",其中不含最高行(第0行)的字符

两种周期的共同点是,每个周期里有h-1个字符,我们把"周期"作为"上周期"和"下周期"的笼统称呼

两种周期的差异点是上周期优先填充(或者说分配)高处行,方向是高到低($0\to h-1$),下周期有限填充低处行,方向是($h-1\to 0$)

现在给定密文长度为n,已知采用深度为h的加密方法

那么完整的"周期"数为$cn{t}_{phase}=\lfloor \frac{n}{h-1}\rfloor$

如果$cn{t}_{phase}$是一个偶数

则上下周期各占一半,$cn{t}_{upperphase}=cn{t}_{lowerphase}=\frac{1}{2}cn{t}_{phase}=\frac{1}{2}\lfloor \frac{n}{h-1}\rfloor$

到此,各行分到的字符数为

cnt[0]=cnt_upperphase;						//最高行只在所有上周期中每个上周期获得一个字符
cnt[1~h-2]=cnt_upperphase+cnt_lowerphase;		//中间行在所有上下周期中都可以每个周期获得一个字符
cnt[h-1]=cnt_lowerphase;					//最低行只在所有下周期中每个下周期获得一个字符

此时剩余没有分配的字符数量为$remain=n-cn{t}_{phase}\times charactersperphase=n-cn{t}_{phase}\times (h-1)=n-\lfloor \frac{n}{h-1}\rfloor \times (h-1)$

如果remain=0说明所有字符恰好被完整个周期分配完毕,否则remain>0说明有剩余字符

这些剩余字符属于一个新的上周期,因此第0到remain-1行各自拿走一个

到此,各行分到的字符数为

cnt[0]=cnt_upperphase+1;						//最高行再获取一个
cnt[1~remain-1]=cnt_upperphase+cnt_lowerphase+1;		//前remain行都各自再获取一个
cnt[remain~h-1]=cnt_upperphase+cnt_lowerphase;			//此后各行保持不变
cnt[h-1]=cnt_lowerphase;					

分配完毕

如果$cn{t}_{phase}$是一个奇数

如果$cn{t}_{phase}$是一个奇数,则上周期比下周期多一个

$cn{t}_{lowerphase}=\lfloor \frac{1}{2}cn{t}_{phase}\rfloor$

$cn{t}_{upperphase}=\lceil \frac{1}{2}cn{t}_{phase}\rceil =cn{t}_{phase}-cn{t}_{lowerphase}$,用计算机取上整数比较麻烦

显然$cn{t}_{phase}$是一个奇数时的计算方法同样适用于偶数
$$\{\begin{array}{l}cn{t}_{phase}=\lfloor \frac{n}{h-1}\rfloor \\ cn{t}_{lowerphase}=\lfloor \frac{1}{2}cn{t}_{phase}\rfloor \\ cn{t}_{upperphase}=\lceil \frac{1}{2}cn{t}_{phase}\rceil =cn{t}_{phase}-cn{t}_{lowerphase}\end{array}$$
到此,各行分到的字符数为

cnt[0]=cnt_upperphase;						//最高行只在所有上周期中每个上周期获得一个字符
cnt[1~h-2]=cnt_upperphase+cnt_lowerphase;		//中间行在所有上下周期中都可以每个周期获得一个字符
cnt[h-1]=cnt_lowerphase;					//最低行只在所有下周期中每个下周期获得一个字符

此时剩余没有分配的字符数量为$remain=n-cn{t}_{phase}\times charactersperphase=n-cn{t}_{phase}\times (h-1)=n-\lfloor \frac{n}{h-1}\rfloor \times (h-1)$

如果remain=0说明所有字符恰好被完整个周期分配完毕,否则remain>0说明有剩余字符

这些剩余字符属于一个新的下周期,因此第h-1到h-2+remain行各自拿走一个

到此各行分到的字符数为

cnt[0]=cnt_upperphase;						
cnt[1~h-remain-1]=cnt_upperphase+cnt_lowerphase		//h-remain-1往上的行不变
cnt[h-remain~h-1]=cnt_upperphase+cnt_lowerphase+1;	//[h-1,h-remain]行均从新的下周期中获得一个字符
cnt[h-1]=cnt_lowerphase+1;					//最低行在新的下周期中获得一个字符

奇数和偶数时的区别

由于奇数时计算周期的公式同样适用于偶数
$$\{\begin{array}{l}cn{t}_{phase}=\lfloor \frac{n}{h-1}\rfloor \\ cn{t}_{lowerphase}=\lfloor \frac{1}{2}cn{t}_{phase}\rfloor \\ cn{t}_{upperphase}=\lceil \frac{1}{2}cn{t}_{phase}\rceil =cn{t}_{phase}-cn{t}_{lowerphase}\end{array}$$
因此在两种情况,只有在处理最后剩下的不完整的新周期时,才有不同,

不同的原因是上下周期分配字符的方向和起点不同

总结成算法O(n)

vector<int> allocate(const int &n, const int &h) { //n个字符,加密深度为hvector<int> cnt(h);int cnt_phase = n / (h - 1);int cnt_lowerphase = cnt_phase / 2;int cnt_upperphase = cnt_phase - cnt_lowerphase;cnt[0] = cnt_upperphase;cnt[h - 1] = cnt_lowerphase;for (int i = 1; i <= h - 2; i++) {cnt[i] = cnt_phase;}int remain = n - cnt_phase * (h - 1);if (remain == 0)return cnt;if (cnt_phase % 2 == 0) {for (int i = 0; i <= remain - 1; ++i)++cnt[i];} else {for (int i = h - 1; i >= h - remain; --i)++cnt[i];}return cnt;
}

以1592468A37为例验证:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> allocate(const int &n, const int &h);//详见上文
int main() {string text = "1592468A37";vector<int> cnt = allocate(text.length(), 3);for (auto i : cnt)cout << i << " ";return 0;
}

结果

3 5 2

是正确的

另一种更简单的cnt数组的计算方式

注意到

vector<int> allocate(const int &n, const int &h);

这个函数并没有获取密码的具体字符信息,而是只给定了密码长度和加密深度,就可以求出一个cnt数组

也就是说,cnt数组和密码是什么字符没有关系

那么我们岂不是可以正着来,直接用加密算法求得cnt数组?

给加密算法encrypt函数传入一个n位长的任意字符串可以求得各行分配到的字符,自然也就求得了各行应该分配的字符个数

也就是说,不管是对123456789还是987654321加密,其排列出的W的形状是相同的

我们现有的加密算法:

string WWW_encrypt(const string &text, const int &h) {string lines[h];int length = text.length();int now = 0;int director;//方向指示标记for (auto c : text) {if (now == 0)director = 1;else if (now == h - 1)director = -1;lines[now] += c;now = now + director;}string encrypted;for (int i = 0; i < h; i++) {encrypted += lines[i];}return encrypted;
}

只需要对其进行一些改造

vector<int> allocate(const int &n, const int &h) {vector<int> cnt(h);int director;//方向指示标记int now = 0;for (int i = 1; i <= n; i++) {if (now == 0)director = 1;else if (now == h - 1)director = -1;++cnt[now];now = now + director;}return cnt;
}

于是同样用$O(n)$甚至更实际更优于前一种的方法出现了

根据cnt数组指示,从密码上连续截取相应数量的字符

根据刚才我们推测得到的算法,

第0行应当截取密码的从0开始,长度为cnt[0]这一段字串encrypted.substr(0,cnt[0]);

第1行应从第0行截取剩下的开始截取,长度为cnt[1]这一字串encrypted.substr(cnt[0],cnt[1])

以此类推,第n行应该截取encrypted.substr(cnt[0]+cnt[1]+....+cnt[n-1],cnt[n])

line[0]=encrypted.substr(0,cnt[0]);
line[n]=encrypted.substr(length,cnt[n]);
length=sum(cnt[0],cnt[1],...,cnt[n-1]);

总结算法:

vector<string> getLines(const string &encrypted, const int &h) {vector<string> line(h);vector<int> cnt = allocate(encrypted.length(), h);line[0] = encrypted.substr(0, cnt[0]);int length = 0;//累加前面的字串长度for (int i = 1; i <= h - 1; i++) {length += cnt[i - 1];//累加line[i] = encrypted.substr(length, cnt[i]);}return line;
}

方向指针解密

现在各行都已经求出来了,得到了我们想象中的这样的结构:

line[0]=	--1---5---9--
line[1]=	---2-4-6-8-A-
line[2]=	----3---7----

实际上是这样的:

line[0]=1,5,9
line[1]=2,4,6,8,A
line[2]=3,7

现在又到了穿针引线的时间,director指示跳转的方向,每行还需要维护一个标记,记录当前行应该取哪个字符了,方便下一次取

什么意思呢?具体来说

注意下标,排名都是从0开始

初始时各行的标记mark[i]=0都是0,意思是,如果要取,肯定从首个(第0个)字符开始

从第0行开始取direction置1,取第0个元素1,++mark[0],意思是第一行的首个元素已经取出,如果下次跳转到第一行取数时应该取下一个元素

按照direction=1下跳到第2行,取第0个元素2,++mark[1],意思时第二行的首个元素已经取出,如果下次跳转到第二行取数时应该取下一元素

按照direction=1下跳到第2行,置direction=-1,取第0个元素3,++mark[2],意思时第二行的首个元素已经取出,如果下次跳转到第二行取数时应该取下一元素

按照direction=-1上跳到第1行,取第1个元素4,++mark[1],意思是第二行的第二个元素已经取出,如果下次跳转到第二行取数时应该取下一元素

…

string decrypt(const string &encrypted, const int &h) {vector<string>line = getLines(encrypted, h);int length = encrypted.length();int director = 0;int now = 0;int mark[h];for (int i = 0; i < h; i++) {mark[i] = 0;//mark数组置0}string decrypted;for (int i = 0; i < length; i++) {if (now == 0)director = 1;else if (now == h - 1)director = -1;decrypted += line[now][mark[now]];++mark[now];//当前行标记后移now += director;//now按照director指示跳转}return decrypted;
}

完整算法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;vector<int> allocate(const int &n, const int &h) { //n个字符,加密深度为hvector<int> cnt(h);int cnt_phase = n / (h - 1);int cnt_lowerphase = cnt_phase / 2;int cnt_upperphase = cnt_phase - cnt_lowerphase;cnt[0] = cnt_upperphase;cnt[h - 1] = cnt_lowerphase;for (int i = 1; i <= h - 2; i++) {cnt[i] = cnt_phase;}int remain = n - cnt_phase * (h - 1);if (remain == 0)return cnt;if (cnt_phase % 2 == 0) {for (int i = 0; i <= remain - 1; ++i)++cnt[i];} else {for (int i = h - 1; i >= h - remain; --i)++cnt[i];}return cnt;}vector<string> getLines(const string &encrypted, const int &h) {vector<string> line(h);vector<int> cnt = allocate(encrypted.length(), h);line[0] = encrypted.substr(0, cnt[0]);int length = 0;for (int i = 1; i <= h - 1; i++) {length += cnt[i - 1];line[i] = encrypted.substr(length, cnt[i]);}return line;
}string decrypt(const string &encrypted, const int &h) {vector<string>line = getLines(encrypted, h);int length = encrypted.length();int director = 0;int now = 0;int mark[h];for (int i = 0; i < h; i++) {mark[i] = 0;}string decrypted;for (int i = 0; i < length; i++) {if (now == 0)director = 1;else if (now == h - 1)director = -1;decrypted += line[now][mark[now]];++mark[now];now += director;}return decrypted;
}int main() {string text = "1592468A37";cout << decrypt(text, 3);return 0;
}