プログラミング応用演習 第 2 回文字列とポインタ
先週のパズルの解説 答え : 全部 p a 1 図の書き方 : p+1 は式であって その値を格納する記憶場所を考えないので 四角で囲まない 2 p+1 同じものを表すいろいろな書き方をしてみましたが パズル以上の意味はありません プログラム中に書くときは p+1 が短くていいんじゃないかな p+1 は 2 の記憶場所 p[1] は 2 に格納されている値 したがって &p[1] は 2 の記憶場所 すなわち p+1 に同じ *p は 1 に格納されている値 &*p は 1 の記憶場所 すなわち p に同じ したがって (&*p)+1 は p+1 に同じ *(p+1) は 2 に格納されている値 したがって &*(p+1) は 2 の記憶場所 すなわち p+1 に同じ p[0] は 1 に格納されている値 &p[0] は 1 の記憶場所 すなわち p に同じ したがって &p[0]+1 は p+1 に同じ
今日のお題 ポインタの利用例 文字列の操作などにポインタを使ってみる 題材として ( 情報セキュリティ学科っぽく ) 暗号化するプログラム 暗号を破るプログラムを考えます
文字列の入力 scanf は 入力文字列を空白で区切ってしまう 便利なこともあるが 機能が多過ぎて使い勝手が悪いこともある 入力された空白や改行を そのまま文字列として読み込むには fgets を使う stdio.h で定義される構造体です char* fgets(char *s, int size, FILE *stream); 入力文字列を格納する記憶場所 入力文字列の最大長さ ( 最後のヌル文字を含む ) 入力元のファイル 標準入力の場合 stdin を指定する
シーザー暗号 文字列と 0~25 の整数を引数に受取り 文字列中のすべての英字を アルファベット順で与えられた数だけ後ろの英字に置き換えて得られる文字列に変換する関数を考える Z の次は A に循環するものとする 例 ) "Hello World!", 5 "Mjqqt Btwqi!"
例 ) 文字列中の英字を k 個ずらす関数 文字の配列を使った場合 ポインタを使った場合 ( 関数のみ ) #include <stdio.h> #define MAXLEN 100 void caesar(char s[], int k) { int i; for(i=0 ; s[i]!= 0 ; i++) { if (('a'<=s[i])&&(s[i]<='z')) { s[i] = (s[i]-'a'+k)%26+'a'; else if (('A'<=s[i])&&(s[i]<='Z')) { int main() { s[i] = (s[i]-'a'+k)%26+'a'; char s[maxlen]; int k; fgets(s,maxlen,stdin); scanf("%d",&k); caesar(s,k); printf("%s",s); return 0; void caesar(char *s, int k) { char *p; for(p=s ; *p!= 0 ; p++) { if (('a'<= *p)&&(*p <='z')) { *p = (*p-'a'+k)%26+'a'; else if (('A'<= *p)&&(*p <='Z')) { *p = (*p-'a'+k)%26+'a'; s p
シーザー暗号を破ってみる S vyfo Xkqkckus! この暗号文から鍵なしで平文が分かるか? シーザー暗号の暗号文は 鍵 ( 整数値 ) k に対して 26-k (mod 26) を鍵とする暗号化と同じ操作をすると 復号される 入力文字列に対して 26 通りの復号すべてを出力するプログラムを考えよう
文字列のコピーを要する 入力された暗号文を異なる鍵で何度も復号 ( 暗号化と同じ操作 ) するので 暗号文を毎回コピーすることを考える ( この問題の場合はコピーしない方法もありえますが ) 暗号を破るプログラムの全体像 : 文字列 ( 暗号文 ) を入力する 鍵を数え挙げる 鍵の一つを k として 以下を繰り返す : 入力文字列をコピーする コピーした文字列を鍵 k で復号する 得られた文字列を出力する
シーザー暗号を破るプログラム #include <stdio.h> #define MAXLEN 100 int main() { int k; char s[maxlen]; fgets(s,maxlen,stdin); for(k=0 ; k<26 ; k++) { char cp[maxlen],*src,*dst; src=s; dst=cp; while(*src!= 0) { 関数 caesar の定義 *dst = *src; dst++; src++; *dst=0; caesar(cp,(26-k)%26); printf("%s",cp); return 0; 鍵の数え挙げ s の内容を cp にコピー 鍵 k での暗号化に対応する復号の鍵 全通り行うので k でもよい おまけのパズル この while 文は C 言語だと while((*dst++=*src++)); と書ける ( セキュアコーディング的観点からはおすすめしない ) なぜ こう書けるか 分かりますか?
シーザー暗号の改造 文字列の他に N 個の整数値 k 0,k 1,...,k N-1 を受け取る 文字列の最初の文字 (0 文字目 ) を k 0 で暗号化し 次の文字 (1 文字目 ) を k 1 で暗号化し...N-1 文字目は k N-1 で暗号化する N 文字目以降の暗号化には 再び k 0 から順に使う 例 ) "Never give up!" を長さ 3 の鍵 5,7,3 で暗号化する : Never give up. 5 7 3 5 7 3 5 7 3 5 7 3 5 7 Slyjy lpyj xu. 文字列 ( 平文 ) と鍵の長さN, およびN 個の整数値を受け取ると 上記の暗号化を行って得られる文字列を出力するプログラムを考えよう
改造版シーザー暗号 鍵が配列 #include <stdio.h> #define MAXLEN 100 #define MAXKEY 6 void caesar2(char *s, int N, int *key){ int ki=0; char *p; for(p=s ; *p!= 0 ; p++) { int k = key[ki]; if (('a'<= *p)&&(*p <='z')) { *p = (*p-'a'+k)%26+'a'; else if (('A'<= *p)&&(*p <='Z')) { *p = (*p-'a'+k)%26+'a'; ki=(ki+1)%n; 鍵の ki 番目の値を使う int main() { int N,key[MAXKEY]; char s[maxlen]; int i; fgets(s,maxlen,stdin); scanf("%d",&n); if ((N < 1) (MAXKEY < N)) { printf("error\n"); return 1; for(i=0 ; i<n ; i++) { scanf("%d",key+i); caesar2(s,n,key); printf("%s",s); return 0; int の配列の要素へのポインタを渡す
改造版シーザー暗号を破ってみる 改造前と同様に全通り出力すればよい (?) N=2 では 26 2 =676 通り N=3 では 26 3 =17,576 通りこれくらいが 人間の目でみてチェックできる限界 平文の長さ 鍵の長さのときは そもそも破れない 暗号文と鍵の長さ (N) が入力されたとき 可能な平文を全通り出力するプログラムを考えよう
入力値 N に対して N 重ループが要る? 26 N 通りの鍵がありうる 0~25 の繰り返しを N 重にすれば全通りを数え挙げられる (?) N は入力値なので プログラムを書いている時点では分からない N 重ループのプログラムは書けない 例えば次のようなプログラミング方法がある : 1 0~26 N -1 の繰り返しをする 2 0~25 の繰り返しの中で再帰呼出しをする
改造版シーザー暗号を破ろうとするプログラム 1 #include <stdio.h> #define MAXLEN 100 #define MAXKEY 6 int power(int x, int y) { int i,r=1; for(i=0 ; i<y ; i++) { r *= x; return r; 関数 caesar2 の定義 x の y 乗の計算 int main() { char s[maxlen]; int N,key[MAXKEY]; int i,pk; fgets(s,maxlen,stdin); scanf("%d",&n); if ((N < 1) (MAXKEY < N)) { printf("error\n"); return 1; pk = power(26,n); for(i=0 ; i<pk ; i++) { char cp[maxlen]; int j,k=i; s を cp にコピーするコード for(j=0 ; j<n ; j++) { key[j] = k%26; k /= 26; caesar2(cp,n,key); printf("%s",cp); 鍵の数え挙げ i 番目の鍵を作る
改造版シーザー暗号を破ろうとするプログラム 2 #include <stdio.h> #define MAXLEN 100 #define MAXKEY 6 void keygen(int N, int n, int *key, char *s){ int i; if (n == N) { char cp[maxlen]; caesar2(cp,n,key); printf("%s",cp); return; for(i=0 ; i<26 ; i++) { 関数 caesar2 の定義 s を cp にコピーするコード key[n] = i; keygen(n,n+1,key,s); return; 再帰の終端で復号して表示 繰り返しの中で再帰呼出し int main() { char s[maxlen]; int N,key[MAXKEY]; int i,pk; fgets(s,maxlen,stdin); scanf("%d",&n); if ((N<1) (MAXKEY<N)) { printf("error\n"); return 1; keygen(n,0,key,s); return 0;
MAXKEY( 鍵の最大長さ ) を 6 にした理由 26 6 =308,915,776 < 2 31 =2,147,483,648 < 26 7 =8,031,810,176 なので 鍵の総数を 32bit の int で表すとすると 鍵の長さは最大 6 改造版シーザー暗号を破ろうとするプログラム 1 は 長さ 7 以上の鍵に対応していない 改造版シーザー暗号を破ろうとするプログラム 2 は 長さ 7 以上の鍵でも動く ただし 何億もの候補を提示されても人間はチェックできないので無意味
出席確認演習 暗号を破りたいとする どんなプログラムがあれば 人間の目で見てチェックする ことの代わりができるだろうか? 周囲の人と議論可 提出方法 :sec02@sun.ac.jp 宛にメール 提出期限 : 今日中
次回予告 構造体