例75 Vigenère 密碼
問題描述
16 世紀法國外交家 Blaise de Vigenère 設計了一種多表密碼加密演算法 Vigenère 密碼，Vigenère 密碼的加密解密演算法簡單易用，且破譯難度比較高，曾在美國南北戰爭中為南軍所廣泛使用，
在密碼學中，我們稱需要加密的資訊為明文，用M表示；稱加密后的資訊為密文，用C表示；而密鑰是一種引數，是將明文轉換為密文或將密文轉換為明文的演算法中輸入的資料，記為k，在Vigenère 密碼中，密鑰k 是一個字母串，k=k1,k2,…,kn，當明文 M=m1,m2,…,mn時，得到的密文 C=c1,c2,…,cn，其中ci =mi?ki，運算?的規則如下表所示：
Vigenère 加密在操作時需要注意：
?運算忽略參與運算的字母的大小寫，并保持字母在明文M中的大小寫形式；
當明文M 的長度大于密鑰 k的長度時，將密鑰 k重復使用，
例如，明文 M=Helloworld，密鑰 k=abc 時，密文 C=Hfnlpyosnd，
輸入
共 2 行，
第一行為一個字串，表示密鑰 k，長度不超過 100，其中僅包含大小寫字母，
第二行為一個字串，表示經加密后的密文，長度不超過 1000，其中僅包含大小寫字母，
輸出
一個字串，表示輸入密鑰和密文所對應的明文，
輸入樣例
CompleteVictory
Yvqgpxaimmklongnzfwpvxmniytm
輸出樣例
Wherethereisawillthereisaway
（1）編程思路1，
定義陣列char table[26][26];保存解密碼表，其中table[i][j]表示密文字符（i+’A’）與密鑰字符（j+’A’）解密所應對應的明文字符，
由運算?規則表可知，字符A解密時，對應解密表應為：
table[0][0]=’A’，
table[0][1]=’Z’（由于加密時，Z?B=A，所以解密時，table[0][1]=’Z’），
同理，table[0][2]=’Y’， table[0][3]=’X’，…，table[0][25]=’B’，
由運算?規則表進一步可知，將字符A的解密表回圈右移1位（由于加密運算表中字符是回圈左移1位的），可得字符B的解密表，即
table[1][0]=’B’，table[1][1]=’A’，table[1][2]=’Z’， table[1][3]=’Y’，…，table[0][25]=’C’，
同理，將字符B的解密表回圈右移1位，可得字符C的解密表，即
table[2][0]=’C’，table[2][1]=’B’，table[2][2]=’A’， table[2][3]=’Z’，…，table[2][25]=’D’，
……
得到了解密碼表后，對于密文中的每個字符，按密鑰和解密碼表直接得到對應的明文字符即可，
為了方便處理，輸入密鑰后，將密鑰中的所有字母全部變成對應的小寫字母，
（2）源程式1，
#include <stdio.h>
#include <string.h>
int main()
{
char table[26][26];
int i,j;
table[0][0]='A';
for (i=1;i<26;i++)
table[0][i]='Z'+1-i;
for (i=1;i<26;i++)
{
for (j=1;j<26;j++)
table[i][j]=table[i-1][j-1];
table[i][0]=table[i-1][25];
}
char keyword[101];
char mess[1001];
scanf("%s%s",keyword,mess);
int len=strlen(keyword);
for (i=0;i<len;i++)
if (keyword[i]>='A' && keyword[i]<='Z')
keyword[i]+=32;
for (i=0;mess[i]!='\0';i++)
{
if (mess[i]>='A' && mess[i]<='Z')
printf("%c",table[mess[i]-'A'][keyword[i%len]-'a']);
else
printf("%c",table[mess[i]-'a'][keyword[i%len]-'a']+32);
}
printf("\n");
return 0;
}
（3）編程思路2，
上面的思路是先按加密運算規則構造好解密碼表，這樣對于每個待解密的字符，直接查表即可，但實際上，仔細分析加密運算規則，可以發現，Vigenère 密碼的加密本質上還是字符移位替換，只不過對于不同的密鑰字符，移位的距離有所不同而已，
例如，對于密鑰字符A，明文字符A~Z加密時，字符保持不變；
對于密鑰字符B，明文字符A~Z加密時，每個字母用其直接后繼的字母（即后面的第1個字母）替換，即字母A用B替換，B用C替換，…，Y用Z替換，Z用A替換；
對于密鑰字符C，明文字符A~Z加密時，每個字母用其后面的第2個字母替換，即字母A用C替換，B用D替換，…，Y用A替換，Z用B替換；
……
也就是，加密時，對于任意的密鑰字符key（設為小寫字母），任意的明文字符mess（為字母A~Z，設也用小寫字母表示）的加密替換運算式為
mess=(mess-‘a’+key-‘a’)%26+’a’
由于解密運算是加密運算的逆運算，因此，對于任意的密鑰字符key（設為小寫字母），任意的密文字符mess（為字母A~Z，設也用小寫字母表示）的解密替換運算式為
mess=(mess-‘a’-(key-‘a’)+26)%26+’a’
=(mess-key+26)%26
這樣，解密時直接按解密替換運算式進行字符替換即可，
（4）源程式2，
#include <stdio.h>
#include <string.h>
int main()
{
char keyword[101];
char mess[1001];
scanf("%s%s",keyword,mess);
int len=strlen(keyword);
int i,j;
for (i=0;i<len;i++) // 將密鑰全部變為小寫
if (keyword[i]>='A' && keyword[i]<='Z')
keyword[i]+=32;
for (i=0,j=0;mess[i]!='\0';i++,j++)
{
if (mess[i]>='a' && mess[i]<='z')
mess[i] = 'a' + (mess[i] - keyword[j] + 26) % 26;
else
mess[i] = 'A' + (mess[i]+32-keyword[j] + 26) % 26;
if (j == len-1) j=-1;
}
printf("%s\n",mess);
return 0;
}
習題75
75-1 密碼破解者
本題選自洛谷題庫 （https://www.luogu.org/problem/P2636）
問題描述
有如下3種加密方式：
一、柵欄密碼：
所謂柵欄密碼，就是把要加密的明文分成L個一組，然后把每組的第1個字連起來，形成一段無規律的話，一般比較常見的是2欄的棚欄密碼，
比如明文：THERE IS A CIPHER
去掉空格后變為：THEREISACIPHER
兩個一組，得到：TH ER EI SA CI PH ER
先取出第一個字母：TEESCPE
再取出第二個字母：HRIAIHR
連在一起就是：TEESCPEHRIAIHR
這樣就得到我們需要的密文了，
但也可能有更多的欄數，
注：若明文長度不能整除欄數，則分組后剩下的單獨為一組，如：
THERE IS A CIPHER 用3欄加密分組為：THE REI SAC IPH ER
先后取出第一二三個字母（最后一組只能取前兩個），加密后為：
TRSIE HEAPR EICH（去掉空格），
二、維吉尼亞(Vigenère)密碼：
維吉尼亞密碼首先應用了“密鑰”的思想，其在密碼屆具有十分重要的意義，
在密碼學中，我們稱需要加密的資訊為明文，用M表示；稱加密后的資訊為密文，用C表示；而密鑰是一種引數，是將明文轉換為密文或將密文轉換為明文的演算法中輸入的資料，記為k，在Vigenère 密碼中，密鑰k 是一個字母串，k=k1,k2,…,kn，當明文 M=m1,m2,…,mn時，得到的密文 C=c1,c2,…,cn，其中ci =mi?ki，運算?的規則如下表所示：
當明文 M 的長度大于密鑰 k 的長度時，將密鑰 k 重復使用，
例如，明文 M=Helloworld，密鑰 k=abc 時，密文 C=Hfnlpyosnd，
三、QWE鍵盤碼：
隨著鍵盤普及，也出現了相應的鍵盤碼，
這是一個常見的鍵盤，在左邊字母區有三行字母分別為：
QWERTYUIOP
ASDFGHJKL
ZXCVBNM
從第一排第一列開始分別用Q替代A，W替代B……，M替代Z以此類推，
如 CODING 加密后即為 EGROFU.
輸入
輸入第一行為一個正整數N 表示截獲的密文共用了N重密碼加密，
第二行為一個字串S表示加密后的密文，
以下3-N+2行共N行每行開頭一個正整數K(1<=K<=3)表示對應的加密方式，
給出的加密方式按順序給出，即給出的第i重加密為實際加密程序的第i重(1<=i<=N)，
若K=1則表示用柵欄密碼加密，之后一個正整數L表示加密所用欄數，
若K=2則表示用維吉尼亞碼加密，之后一個字串T表示密鑰，
若K=3則表示用QWE鍵盤碼加密，
輸出
共一行，一個字串，表示破解N重加密后的明文，
輸入樣例
2
YSLTRIQXSHTQTR
1 2
3
輸出樣例
FULLSPEEDAHEAD
（1）編程思路，
一共就三種加密方式，撰寫三個對應的函式進行解密，其中：
函式void Fence(int L)對加密時明文分成L個一組所生成的密文進行解密，
函式void Vigenere(char *keyword)對用密鑰keyword進行加密后的密文進行解密，采用例75中給出的解密替換運算式進行解密，
函式void QWE()實作對采用QWE鍵盤碼加密的密文進行解密，把QWE鍵盤碼的順序和字母ABCD相對應，得到解密碼表為char qwe[] = "kxvmcnophqrszyijadlegwbuft";，
在進行解密時，要按照加密順序進行反向解密，例如，加密順序是1、3，解密順序應為3、1，
（2）源程式，
#include <stdio.h> #include <string.h> char mess[30005]; char key[1001][1001]; void Fence(int L) { int i,j,k; char temp[30005]; int len=strlen(mess); for (i=0,j=0,k=0;i<len; i++,j+=L) { if (j>=len) j=++k; temp[j] = mess[i]; } strcpy(mess,temp); } void Vigenere(char *keyword) { int len=strlen(keyword); int i,j; for (i=0;i<len;i++) // 將密鑰全部變為小寫 if (keyword[i]>='A' && keyword[i]<='Z') keyword[i]+=32; for (i=0,j=0;mess[i]!='\0';i++,j++) { if (mess[i]>='a' && mess[i]<='z') mess[i] = 'a' + (mess[i] - keyword[j] + 26) % 26; else mess[i] = 'A' + (mess[i]+32-keyword[j] + 26) % 26; if (j == len-1) j=-1; } } void QWE() { char qwe[] = "kxvmcnophqrszyijadlegwbuft"; int i; for (i=0; mess[i]!='\0';i++) { if (mess[i]>='a' && mess[i]<='z') mess[i] = qwe[mess[i] - 'a']; else mess[i] = qwe[mess[i]+32-'a']-32; } } int main() { int n; scanf("%d",&n); scanf("%s",mess); int op[1001],L[1001]; int i; for (i=1;i<=n;i++) { scanf("%d",&op[i]); if (op[i]==1) scanf("%d",&L[i]); if (op[i]==2) scanf("%s",key[i]); } for (i=n;i>=1;i--) { if (op[i]==1) Fence(L[i]); if (op[i]==2) Vigenere(key[i]); if (op[i]==3) QWE(); } printf("%s\n",mess); return 0; }View Code
75-2 SRL加密
問題描述
設有SRL（Shake，Rattle and rolL）加密方法如下：
待加密的文本資訊按行主順序放入一個n階方陣中，每個字符位于方陣唯一的單元格中，如果資訊沒有完全填滿方陣，空單元格將填充字母表的大寫字母，從字母A開始，一直到字母Z（根據需要重復），例如，6階方陣中的資訊“Meet me at the pizza parlor”將如下圖所示，注意，所有字符都存盤為大寫字母，
要加密此資訊，將執行3個單獨的操作，如下所示：
1）S（Shake）操作：方陣中每個奇數列向上移動一個字符，最上面的字符移動到該列的底部，每個偶數列向下移動，最底部的字符移動到列的頂部，列從1開始編號，如下圖所示，
2）R（Rattle）操作：方陣中每個奇數行向右移動一個字符，最右邊的字符移動到同一行最左邊的列，每個偶數行向左移動一個字符，最左邊的字符移動到同一行中最右邊的列，行從頂部1開始編號，如下圖所示，
3）L（roll）操作：方陣周圍的每個奇數“圈”順時針旋轉一個字符，而每個偶數“圈”逆時針旋轉一個字符，如下圖所示，“圈”號標記為“圈”的最上面一行的行號（最上面一行是第1行），即最外一“圈”為第1圈，
方陣大小在加密密鑰中指定，大小從3x3到100x100不等，
輸入
輸入包括多個測驗用例，每個測驗用例占兩行，其中第一行是加密密鑰，第二行是要加密的文本資訊，加密密鑰總是以兩位數的方陣大小開始，“00”的大小解釋為100；然后是一系列任意順序的“S”、“R”或“L”字符，對于每個字符，將執行相應的操作，例如，對于每個“R”字符，將執行“R（Rattle）”操作，
加密密鑰限制為80個字符，待加密的文本資訊限制為10000個字符，假設資訊始終適合指定的方陣，
輸出
每個測驗用例輸出加密后的文本資訊，加密后文本資訊的長度是方陣階數的平方（例如，3階方陣產生長度為9的加密字串），
輸入樣例
04RSRR
I love ice cream
06SRL
Meet me at the Pizza Parlor
輸出樣例
IREAELCIMVE OC
EIEEAGTTIMT E P ZHRZB PAORDAFLEA CMH
（1）編程思路，
撰寫void shake(char (*a)[110], int n)和void rattle(char (*a)[110], int n)分別模擬S操作和R操作，這兩個操作的實作比較簡單，若將一個二維陣列的一行或一列看成是一個一維陣列，則這個兩個操作的實作本質上就是將一個一維陣列的各元素回圈左移（或右移）1位，
將有n個元素的一維陣列a回圈左移1位，可以寫成如下的一重回圈
T=a[0];
for (i=1;i<n;i++) a[i-1]=a[i];
a[n-1]=t;
而將有n個元素的一維陣列a回圈右移1位，可以寫成如下的一重回圈
T=a[n-1];
for (i=n-1;i>0;i--) a[i]=a[i-1];
a[0]=t;
撰寫函式void roll(char (*a)[110], int n)實作L（roll）操作，這個操作的實作比前2個操作的實作稍微麻煩一些，
一個n階方陣可以看成由n/2圈組成，例如，4階方陣由2圈組成，5階方陣實際上由3圈組成，但最內圈只有1個元素，忽略掉最內圈的1個數的話，5階方陣也可以看成由2圈組成，
進行L操作時，方陣周圍的每個奇數“圈”順時針旋轉一個字符，而每個偶數“圈”逆時針旋轉一個字符，一圈順時針旋轉可以看成是兩行和兩列的移位操作，
例如，最外圈順時針旋轉一個字符，可以看成頂行字符右移1位，最右列字符向下移1位，最底行字符左移1位，最左列字符向上移1位，具體實作時，先保存最外圈最左上角的字符（t=a[0][0]），然后，最左列字符向上移1位，最底行字符左移1位，最右列字符向下移1位，頂行字符右移1位，最后將保存的t賦給a[0][1]即可，
逆時針操作的實作與順時針類似，參見源程式，
（2）源程式，
#include <stdio.h> #include <string.h> char mat[110][110]; void shake(char (*a)[110], int n) { int i, j; char temp; for (i=0; i<n; i++) { if (i%2==0) { temp = a[0][i]; for (j=1; j<n; j++) a[j-1][i] = a[j][i]; a[n-1][i] = temp; } else { temp = a[n-1][i]; for (j = n-1; j > 0; j--) a[j][i] = a[j-1][i]; a[0][i] = temp; } } } void rattle(char (*a)[110], int n) { int i, j; char temp; for (i = 0; i < n; i++) { if (i%2 == 0) { temp = a[i][n-1]; for (j = n-1; j > 0; j--) a[i][j] = a[i][j-1]; a[i][0] = temp; } else { temp = a[i][0]; for (j = 1; j < n; j++) a[i][j-1] = a[i][j]; a[i][n-1] = temp; } } } void roll(char (*a)[110], int n) { int i,j,num,k; char temp; num = n/ 2; for (k = 0; k < num; k++,n--) { if (k%2==0) { j = i = k; temp = a[i][j]; i++; while (i < n) { a[i-1][j] = a[i][j]; i++; } i--; j++; while (j < n) { a[i][j-1] = a[i][j]; j++; } j--; while (i > k) { a[i][j] = a[i-1][j]; i--; } while (j > k+1) { a[i][j] = a[i][j-1]; j--; } a[i][j] = temp; } else { j = i = k; temp = a[i][j]; j++; while (j < n) { a[i][j-1] = a[i][j]; j++; } j--; i++; while (i < n) { a[i-1][j] = a[i][j]; i++; } i--; while (j > k) { a[i][j] = a[i][j-1]; j--; } while (i > k+1) { a[i][j] = a[i-1][j]; i--; } a[i][j] = temp; } } } int main() { char key[81],mess[10005]; while (scanf("%s",key)!=EOF) { getchar(); gets(mess); int len1 = strlen(key); int len2 = strlen(mess); // 求出矩陣大小，注意00代表100！ int size = (key[0]-'0')*10 + key[1]-'0'; if (size == 0) size = 100; int i,j; for (i=len2, j=0; i<size*size; i++, j++) mess[i]='A'+j%26; mess[i]='\0'; int k = 0; for (i = 0; i < size; i++) for (j = 0; j < size; j++) { mat[i][j] = mess[k]; k++; } for (i=2; i<len1; i++) { if (key[i]=='S') shake(mat,size); else if (key[i] == 'R') rattle(mat,size); else if (key[i] == 'L') roll(mat, size); } for (i = 0; i < size; i++) { for (j = 0; j < size; j++) { if (mat[i][j]>='a' && mat[i][j]<='z') mat[i][j]= mat[i][j]-'a'+'A'; printf("%c",mat[i][j]); } } printf("\n"); } return 0; }View Code
75-3 不可靠訊息
問題描述
某王國的國王選了六名仆人作為信使，他們的名字是J先生、C小姐、E先生、A先生、P先生和M先生，某位信使收到給國王的訊息后，他們會向下一位信使傳遞訊息，直到訊息傳到國王手中，
給國王的訊息由數字（'0'-'9'）和字母（'A'-Z'，'a'-'z'）組成，大寫字母和小寫字母在訊息中是有區別的，例如，“ke3E9Aa”是一條訊息，
因為每個信使在將訊息傳遞給下一個信使（或國王）之前都會稍微更改訊息，這樣國王總是收到錯誤的訊息，這激怒了國王，他要求王宮主管想辦法來糾正它，為了完成國王的任務，主管仔細分析了信使的錯誤，并獲得了每個信使錯誤的特征，令人驚訝的是，每位信使在轉發訊息時都只會犯同樣的錯誤，觀察到以下事實，
J先生將訊息的所有字符向左旋轉一位，例如，他將“aB23d”轉換為“B23da”，
C小姐將訊息的所有字符向右旋轉一個，例如，她將“aB23d”轉換為“daB23”，
E先生將訊息的左半部與右半部交換，如果訊息的字符數為奇數，則中間的字符不會移動，例如，他將“e3ac”轉換為“ace3”，將“aB23d”轉換為“3d2aB”，
A先生顛倒了訊息，例如，他將“aB23d”轉換為“d32Ba”，
P先生將訊息中的所有數字遞增1，如果一個數字是“9”，它就變成了“0”，字母不變，例如，他將“aB23d”轉換為“aB34d”，將“e9ac”轉換為“e0ac”，
M先生將訊息中的所有數字遞減一，如果一個數字是“0”，它就變成了“9”，字母不變，例如，他將“aB23d”轉換為“aB12d”，將“e0ac”轉換為“e9ac”，
請撰寫程式，根據信使的順序，從最后的訊息中推斷出原始訊息，例如，如果送信人依次是A->J->M->P，而給國王的訊息是“aB23d”，那么最初的資訊是什么？根據信使錯誤的特點，導致最終訊息的順序是“32Bad”->“daB23”->“aB23d”->“aB12d”->“aB23d”：因此，原始訊息應該是“32Bad”，
輸入
輸入的第一行包含一個正整數n，表示測驗用例的數量，每個測驗用例包括兩行，第1行是傳遞訊息的信使順序，第2行是最后給國王的訊息，轉發訊息的信使數在1到6之間（含1到6），同一個信使不會出現多次，訊息的長度介于1和25之間（含1和25），
輸出
對于每個測驗用例，輸出原始訊息，
輸入樣例
5
AJMP
aB23d
E
86AE
AM
6
JPEM
WaEaETC302Q
CP
rTurnAGundam1isdefferentf
輸出樣例
32Bad
AE86
7
EC302QTWaEa
TurnAGundam0isdefferentfr
（1）編程思路，
分別撰寫6個函式void Jfun(char str[])、void Cfun(char str[])、void Efun(char str[])、void Afun(char str[])、void Pfun(char str[])和void Mfun(char str[])來模擬處理J先生、C小姐、E先生、A先生、P先生和M先生的變換操作，每個函式的實作都是一個簡單的一重回圈，具體參見源程式，
（2）源程式，
#include <stdio.h> #include <string.h> void Jfun(char str[]) { int i; char t; t=str[0]; for (i=1;str[i]!='\0';i++) { str[i-1]=str[i]; } str[i-1]=t; } void Cfun(char str[]) { int i,len; char t; len=strlen(str); t=str[len-1]; for (i=len-2;i>=0;i--) { str[i+1]=str[i]; } str[0]=t; } void Efun(char str[]) { int i,j,t; i=0; j=(strlen(str)+1)/2; while (str[j]!='\0') { t=str[i]; str[i]=str[j]; str[j]=t; i++; j++; } } void Afun(char str[]) { int i,j,t; for (i=0,j=strlen(str)-1;i<j;i++,j--) { t=str[i]; str[i]=str[j]; str[j]=t; } } void Pfun(char str[]) { int i; for (i=0; str[i]!='\0';i++) if (str[i]>='0'&& str[i]<='8') str[i]++; else if (str[i]=='9') str[i]='0'; } void Mfun(char str[]) { int i; for (i=0; str[i]!='\0';i++) if (str[i]>='1'&& str[i]<='9') str[i]--; else if (str[i]=='0') str[i]='9'; } int main() { char str[30],s[8]; int n,i; scanf("%d",&n); while (n--) { scanf("%s%s",s,str); for (i=strlen(s)-1;i>=0;i--) { switch(s[i]) { case 'J':Cfun(str);break; case 'C':Jfun(str);break; case 'E':Efun(str);break; case 'A':Afun(str);break; case 'P':Mfun(str);break; case 'M':Pfun(str);break; } } printf("%s\n",str); } return 0; }View Code
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/438627.html
標籤：其他
下一篇：C++記憶體磁區模型