PowerPoint プレゼンテーション

Transcription

1 プログラミング応用演習 第 2 回文字列とポインタ

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 に同じ

3 今日のお題 ポインタの利用例 文字列の操作などにポインタを使ってみる 題材として ( 情報セキュリティ学科っぽく ) 暗号化するプログラム 暗号を破るプログラムを考えます

4 復習 : 文字列 C 言語では 文字列は文字の配列 最後に \0( ヌル文字 ) がある 文字を表す型が char なので 文字列は char の配列 文字列定数は "( ダブルクォート ) で括って表す文字 文字コードという整数値に対応している 文字を整数として計算したり比較したりできる 文字コードを計算 比較している 文字定数は '( シングルクォート ) で括って表す アルファベットは文字コード中で並んでいる 例えば 'A'+1 は 'B' に等しい

5 復習 : ポインタと配列 配列の名前は 先頭の要素へのポインタ値を表す 例 ) char s[10]; と宣言したとき s は s[0] の記憶場所を表す 配列の要素はメモリ中で連続している 例 ) char s[10]; と宣言したとき s[0], s[1], s[2]... の記憶場所は連続している ポインタへの整数の加減算は 配列の添字の加減算に対応する 例 )char s[10],*p=s; と宣言 ( と初期代入 ) したとき p+1 は s[1] の記憶場所を p+2 は s[2] の記憶場所をそれぞれ表す

6 文字列の入力 scanf は 入力文字列を空白で区切ってしまう 便利なこともあるが 機能が多過ぎて使い勝手が悪いこともある 入力された空白や改行を そのまま文字列として読み込むには fgets を使う stdio.h で定義される構造体 char* fgets(char *s, int size, FILE *stream); 入力文字列を格納する記憶場所 入力文字列の最大長さ ( 最後のヌル文字を含む ) 入力元のファイル 標準入力の場合 stdin を指定する

7 シーザー暗号 文字列と 0~25 の整数を引数に受取り 文字列中のすべての英字を アルファベット順で与えられた数だけ後ろの英字に置き換えて得られる文字列に変換する関数を考える Z の次は A に循環するものとする 例 ) "Hello World!", 5 "Mjqqt Btwqi!"

8 例 ) 文字列中の英字を 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')) { s p *p = (*p-'a'+k)%26+'a'; else if (('A'<= *p)&&(*p <='Z')) { *p = (*p-'a'+k)%26+'a';

9 シーザー暗号を破ってみる S vyfo Xkqkckus! この暗号文から鍵なしで平文が分かるか? シーザー暗号の暗号文は 鍵 ( 整数値 ) k に対して 26-k (mod 26) を鍵とする暗号化と同じ操作をすると 復号される 入力文字列に対して 26 通りの復号すべてを出力するプログラムを考えよう

10 文字列のコピーを要する 入力された暗号文を異なる鍵で何度も復号 ( 暗号化と同じ操作 ) するので 暗号文を毎回コピーすることを考える ( この問題の場合はコピーしない方法もありえますが ) 暗号を破るプログラムの全体像 : 文字列 ( 暗号文 ) を入力する 鍵を数え挙げる 鍵の一つを k として 以下を繰り返す : 入力文字列をコピーする コピーした文字列を鍵 k で復号する 得られた文字列を出力する

11 シーザー暗号を破るプログラム #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++)); と書ける ( セキュアコーディング的観点からはおすすめしない ) なぜ こう書けるか 分かりますか?

12 シーザー暗号の改造 文字列の他に 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 Slyjy lpyj xu. 文字列 ( 平文 ) と鍵の長さN, およびN 個の整数値を受け取ると 上記の暗号化を行って得られる文字列を出力するプログラムを考えよう

13 改造版シーザー暗号 鍵が配列 #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 の配列の要素へのポインタを渡す

14 改造版シーザー暗号を破ってみる 改造前と同様に全通り出力すればよい (?) N=2 では 26 2 =676 通り N=3 では 26 3 =17,576 通りこれくらいが 人間の目でみてチェックできる限界 平文の長さ 鍵の長さのときは そもそも破れない 暗号文と鍵の長さ (N) が入力されたとき 可能な平文を全通り出力するプログラムを考えよう

15 入力値 N に対して N 重ループが要る? 26 N 通りの鍵がありうる 0~25 の繰り返しを N 重にすれば全通りを数え挙げられる (?) N は入力値なので プログラムを書いている時点では分からない N 重ループのプログラムは書けない 例えば次のようなプログラミング方法がある : 1 0~26 N -1 の繰り返しをする 2 0~25 の繰り返しの中で再帰呼出しをする

16 改造版シーザー暗号を破ろうとするプログラム 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); return 0; 鍵の数え挙げ i 番目の鍵を作る

17 改造版シーザー暗号を破ろうとするプログラム 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]; fgets(s,maxlen,stdin); scanf("%d",&n); if ((N<1) (MAXKEY<N)) { printf("error\n"); return 1; keygen(n,0,key,s); return 0;

18 実験の仕方 : リダイレクトとパイプ こんなファイルを作る プログラムに入力する文字列を記述したもの 3 のあとの改行を忘れないように プログラムに入力する値を流し込む ( リダイレクト )./a.out < test Slyjy lpyj xu. 3 ファイルの名前は何でもよいが ここでは test としておく 出力を less コマンドに渡す ( パイプ )./a.out < test less

19 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 以上の鍵でも動く ただし 何億もの候補を提示されても人間はチェックできないので無意味

20 実行してみよう 以下の暗号を解読してください ただし 改造版シーザー暗号で鍵の長さが 2 と分かっている Ol h nelna wevtyntzle!

21 次回予告 構造体