C语言程序设计100例之（74）：柱状加密
例74 柱状加密
问题描述
柱状加密方案是使用密钥对消息（或明文）中的字母进行置乱，如下例所示。
假设密钥是“BATBOY”，消息明文是“MEET ME BY The OLD OAK TREE”。由于密钥有6个字母，我们将消息（忽略空格和标点符号）写在一个有6列的网格中，根据需要用随机的额外字母填充，结果如下：
MEETME
BYTHEO
LDOAKT
REENTH
在这里，我们用NTH填充了消息。现在，密文是按列生成的，但列的打印顺序由密钥中的字母决定。因为密钥中的A是字母表中第一个字母，所以第2列首先输出。下一个字母B出现两次。在这种情况下，先输出最左边的列（第1列），然后输出第4列。之后，继续按字母O、T、Y的顺序输出第5、3、6列。由于列的输出顺序是2、1、4、5、3、6。所以，密文为EYDEMBLRTHANMEKTETOEEOTH。
编写程序，根据给定的密钥和密文，解密得到明文。
输入
输入包括多组测试用例。每组测试用例有两行。第一个输入为给定密钥，该密钥不超过10个字符，由大写字母组成。第二行是密文，长度不超过100个字符，全部也由大写字母组成。密钥THEEND表示输入结束，在这种情况下，将没有密文跟随。
输出
对于每个测试用例，输出解密后的明文。
输入样例
BATBOY
EYDEMBLRTHANMEKTETOEEOTH
HUMDING
EIAAHEBXOIFWEHRXONNAALRSUMNREDEXCTLFTVEXPEDARTAXNAARYIEX
THEEND
输出样例
MEETMEBYTHEOLDOAKTREENTH
ONCEUPONATIMEINALANDFARFARAWAYTHERELIVEDTHREEBEARSXXXXXX
（1）编程思路。
先定义结构体
struct Elem
{
char ch;
int index;
};
其中，成员分量ch表示密钥中的某个字母，index表示该字母对应的列号。
定义结构体数组struct Elem letter[15]，输入密钥后，将密钥中的每个字母及该字母对应的列号保存为数组letter中的一个元素，将数组letter按成员分量字符ch从小到大排序，这样，加密时列的顺序也就得到了，将这个加密列号的顺序保存到数组int map[15];中，其中map[0]的值就是加密时所取的第1个列的列号。
加密时，密文是按列生成的。加密所用的矩阵行数row=(密文的长度)/(密钥的长度)。
设输入的密文字符串为cipher，则解密时，依次从该字符串对应的矩阵中按行的顺序，在每行中按加密密钥指定的列号顺序（已求得并存入map数组中），取出字符顺序填入到明文字符串中即可。这个处理过程对应的循环为
n=0;
for (i=0; i { for (j = 0; j plain[n++]=cipher[i + map[j] * row]; } plain[n]='\0'; #include #include struct Elem { char ch; int index; }; int main() { struct Elem letter[15],t; char key[15],cipher[105],plain[105]; int key_len,map[15]; int i,j,n,row; while (gets(key), strcmp(key, "THEEND")!=0) { gets(cipher); key_len = strlen(key); for (i = 0; i < key_len; i++) { letter[i].ch = key[i]; letter[i].index = i; } for (i=0;i for (j=0;j if (letter[j].ch>letter[j+1].ch) { t=letter[j]; letter[j]=letter[j+1]; letter[j+1]=t; } for (i = 0; i map[letter[i].index] = i; row = strlen(cipher) / key_len; n=0; for (i=0; i { for (j = 0; j plain[n++]=cipher[i + map[j] * row]; } plain[n]='\0'; printf("%s\n",plain); } return 0; } 问题描述 Mo和Larry发明了一种信息加密方法。他们首先决定好列数，然后将信息（只包含字母）从上往下依次填入各列，并在末尾补充一些随机字母使其成为一个完整的字母矩阵。例如，若信息是“There's no place like home on a snowy night”并且有5列，Mo会写成： t o i o y h p k n n e l e a i r a h s g e c o n h s e m o t n l e w x 注意Mo只会填入字母，且全部是小写形式。在这个例子中，Mo用字母“x”填充了信息使之成为一个完整的矩阵，当然他使用任何字母都是可以的。 Mo根据这个矩阵重写信息：首先从左到右写下第一行，然后从右到左写下第二行，再从左到右写下第三行……以此左右交替地从上到下写下各行字母，形成新的字符串。这样，例子中的信息就被加密为：toioynnkpheleaigshareconhtomesnlewx。 你的工作是帮助Larry从加密后的信息中还原出原始信息（包括填充的字母）。 输入 第一行包含一个整数（范围2到20），表示使用的列数。 第二行是一个长度不超过200的字符串。 输出 一行，即原始信息。 输入样例 toioynnkpheleaigshareconhtomesnlewx 输出样例 theresnoplacelikehomeonasnowynightx （1）编程思路。 定义二维字符串数组char mess[101][21]来保存密文字符串所对应的字符矩阵。 先将输入的密文字符串中的每个字符按照先从左到右，然后再从右到左的顺序逐行依次填入到数组mess中，之后按列序优先的方式（每列从上到下）依次输出mess数组中的每个字符，就是解密后的原文。 （2）源程序。 #include int main() { char mess[101][21],src[201]; int row,col,i,j,d; // d代表方向，1从左向右，0从右向左 scanf("%d",&col); scanf("%s",src); i=0,row=0,j=-1,d=1; while (src[i]!='\0') { if (d==1) { j++; if (j==col) { row++; j=col-1; d=0; } } else { j--; if (j==-1) { row++; j=0; d=1; } } mess[row][j]=src[i]; i++; } for (j=0;j for (i=0;i<=row;i++) printf("%c",mess[i][j]); printf("\n"); return 0; } 问题描述 密码学涉及秘密通信的方法，这些方法将消息（明文）转换为伪装形式（密文），这样，除了预期的接收者，看到密文的人将无法识别明文。将明文转换为密文是加密；将密文转换为明文就是解密。变换是一种简单的加密方法，要求发送方和接收方都同意一个密钥K，它是一个正整数。 变换加密方法使用四个数组：明文plaintext和密文ciphertext是字符数组，而明码plaincode和密码ciphercode是整数数组。所有数组的长度都是n，其中n是要加密的消息的长度。数组的下标起始为零，因此下标编号从0到n-1。对于这个问题，所有消息（明文）中将只包含小写字母、句点和下划线（表示空格）。 要加密的消息以明文形式存储。给定密钥K，加密方法如下所示。首先根据以下规则将明文中的字母转换为明文中的整数码：'_'=0，'a'=1，'b'=2，'z'=26和'.'=27。接下来，根据以下公式将每个明码转换为加密密码：对于从0到n-1的所有i， ciphercode[i] = (plaincode[K*i mod n] - i) mod 28.。 （这里x mod y是x除以y时的正余数。例如，3 mod 7=3、22 mod 8=6和-1 mod 28=27。如果结果为负，要加上y。）最后，根据上面列出的规则将密码中的代码转换回密文中的字母。 使用密钥K=5对明文信息“cat”加密过程如下： 数组下标 0 1 2 明文plaintext c a t 明码plaincode 3 1 20 密码ciphercode 3 19 27 密文ciphertext c s . 编写一个可以解密的程序，即给定密钥K，将密文转换回原始明文。 输入 输入包含一个或多个测试用例，后跟一行，该行仅包含表示文件结束的数字0。每个测试用例占一行，由密钥K、空格和一条至少包含一个且最多70个字符的密文组成。密钥K将是不大于300的正整数。 输出 对于每个测试用例，在一行上输出对应的明文。 输入样例 5 cs. 101 thqqxw.lui.qswer 3 b_ylxmhzjsys.virpbkr 输出样例 cat this_is_a_secret beware._dogs_barking （1）编程思路。 按题目的描述定义4个数组，按加密过程的描述进行相应处理即可。 （2）源程序。 #include #include int mod(int a,int b) { return (a%b+b)%b; } int main() { char plaintext[75],ciphertext[75]; int plaincode[75],ciphercode[75]; int k,i,len; while (scanf("%d",&k) && k!=0) { scanf("%s",ciphertext); len=strlen(ciphertext); for (i=0;ciphertext[i]!='\0';i++) { if (ciphertext[i]>='a' && ciphertext[i]<='z') ciphercode[i]=ciphertext[i]-'a'+1; else if (ciphertext[i]=='_') ciphercode[i]=0; else if (ciphertext[i]=='.') ciphercode[i]=27; } for (i=0;i { plaincode[mod(k*i,len)]=mod(ciphercode[i]+i,28); } for (i=0;i if (plaincode[i]>=1 && plaincode[i]<=26) plaintext[i]=plaincode[i]-1+'a'; else if (plaincode[i]==0) plaintext[i]='_'; else plaintext[i]='.'; plaintext[len]='\0'; printf("%s\n",plaintext); } return 0; } 问题描述 Alice向Bob发来了一条混乱的信息，Bob请你进行破译。Alice发送消息使用的置乱方法如下： 1）获取一条非空消息M，其中包含英文字母表中的字母、数字、逗号、点、引号（’）、空格和换行符，最后一个字符不是空格。例如，考虑下面的信息M In Sneffels craterem descende audas viator, et terrestre centrum attinges. 2）选择一个整数K（0 3）将M'中的所有空格替换为字符“_”（下划线），将M'中的所有换行符替换为“\”（反斜杠），然后反转消息如下： __.segnitta_murtnec_ertserret_te_,rotaiv\sadua_ednecsed_meretarc_sleffenS_nI 4）将步骤3的结果写入一个长度为（M'的长度）/K行和K列的表格中。例如，上面的消息M’被写入一个76/19=4行19列的表中，如下所示： 5）Alice将与表中的行相对应的字符串作为加密消息M的片段发向Bob。所发送信息的4个片段是： _etmneet_t\udsmt_fS _gtuerr_,asaneeasf_ .narctrtria_edrrlen si_t_seeovdec_ecenI 编写一个程序，破译按上述方式加密的非空消息。在加密之前，消息的长度最多为1000个字符，包括空格和换行符。 输入 输入包括多组测试用例，每个测试用例对应一条加密消息。一个测试用例以整数n开始，该整数显示被加密消息的片段数，并以指定片段的n个字符串继续，其顺序与加密过程第4步表中出现的顺序相同。输入数据片段以空格分隔。输入以文件结尾结束。 输出 解密后的信息必须打印在标准输出上，从一行开始，后面必须有空行，如下面的输入/输出样例所示。 输入样例 4 _etmneet_t\udsmt_fS _gtuerr_,asaneeasf_ .narctrtria_edrrlen si_t_seeovdec_ecenI 11 e n r e V _ s e l u J 输出样例 In Sneffels craterem descende audas viator, et terrestre centrum attinges. Jules Verne （1）编程思路。 将输入的加密信息片段存放到二维数组中，由于加密时实际上是将明文字符串从右至左，从下至上存入二维表格中的，因此解密是将二维数组中保存的字符也按从右至左，从下至上依次取出保存在结果字符串中即可，保存的同时字符“_”变成空格，“\”变成回车符“\n”。最后去掉尾部多添加的空格。 （2）源程序。 #include #include int main() { int n; while(scanf("%d",&n)!=EOF) { char ch[1001][1001]; char res[1001]; memset(res,0,sizeof(res)); int i,j; for (i=0;i { scanf("%s",ch[i]); } int len=strlen(ch[0]); int pos=0; for (i=len-1;i>=0;i--) { for (j=n-1;j>=0;j--) { if (ch[j][i]=='_') res[pos++]=' '; else if (ch[j][i]=='\\') res[pos++]='\n'; else res[pos++]=ch[j][i]; } } for (i=pos-1;res[i]==' ';i--) // 去掉尾部多添加的空格 res[i]='\0'; printf("%s\n\n",res); } return 0; }（2）源程序。
习题74
74-1 信息加密
74-2 变换加密
74-3 消息解密