PowerPoint プレゼンテーション

プログラミング応用演習

第2回 文字列とポインタ

先週のパズルの解説 答え：全部

2017.04.19

①

②

a

●

p+1 は

②

の記憶場所。

●

p[1]は

②

に格納されている値。

したがって、&p[1]は

②

の記憶場所、

すなわち、p+1に同じ。

●

*p は

①

に格納されている値。&*pは

①

_{の記憶場所、すなわち p に同じ。}

したがって(&*p)+1 は p+1 に同じ。

●

*(p+1)は

②

に格納されている値。

したがって、&*(p+1)は

②

の記憶場所、

すなわち、p+1に同じ。

●

p[0]は

①

に格納されている値。&p[0]

は

①

_{の記憶場所、すなわち p に同じ。}

したがって &p[0]+1 は p+1 に同じ。

p

p+1

※ 同じものを表すいろいろな書

き方をしてみましたが、パズル

以上の意味はありません。プロ

グラム中に書くときは、p+1 が

短くていいんじゃないかな。

今日のお題



ポインタの利用例



文字列の操作

など

にポインタを使ってみる

題材として（情報セキュリティ学科っぽく）、



暗号化するプログラム



暗号を破るプログラム

を考えます。

2017.04.19

文字列の入力

scanf は、入力文字列を空白で区切ってしまう。



便利なこともあるが、機能が多過ぎて使い勝手

が悪いこともある

入力された空白や改行を、そのまま文字列として

読み込むには、fgets を使う。

char* fgets(char *s, int size, FILE *stream);

2017.04.19

入力文字列を格納

する記憶場所

入力文字列の最大

長さ（最後のヌル

文字を含む）

入力元のファイル。

標準入力の場合、

stdin を指定する。

stdio.hで定義される

構造体です。

シーザー暗号

文字列と 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')) { s[i] = (s[i]-'A'+k)%26+'A'; } } } int main() { char s[MAXLEN]; int k; fgets(s,MAXLEN,stdin); scanf("%d",&k); caesar(s,k); printf("%s",s); return 0; }

2017.04.19

【文字の配列を使った場合】

【ポインタを使った場合（関数のみ）】

s

p

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 vyfo Xkqkckus!

↑この暗号文から鍵なしで平文が分かるか？

シーザー暗号の暗号文は、鍵(整数値) k に

対して、26-k

(mod 26)

を鍵とする暗号化と

同じ操作をすると、復号される。

入力文字列に対して、26通りの復号すべてを

出力するプログラムを考えよう。

2017.04.19

文字列のコピーを要する

入力された暗号文を異なる鍵で何度も復号（暗号化

と同じ操作）するので、暗号文を毎回コピーするこ

とを考える。

(この問題の場合はコピーしない方法もありえますが…)

暗号を破るプログラムの全体像：



文字列（暗号文）を入力する



鍵を数え挙げる。鍵の一つを k として、以下を繰り返す：



入力文字列をコピーする



コピーした文字列を鍵 k で復号する



得られた文字列を出力する

2017.04.19

シーザー暗号を破るプログラム

2017.04.19

関数 caesar の定義

鍵の数え挙げ

s の内容を

cp にコピー

鍵kでの暗号化に対

応する復号の鍵。

全通り行うので、k

でもよい。

シーザー暗号の改造

文字列の他に N個の整数値 k

₀

,k

₁

,...,k

_N-1

を受け取る。

文字列の最初の文字(0文字目)をk

₀

で暗号化し、次の文字(1文

字目)をk

₁

で暗号化し...N-1文字目はk

_N-1

で暗号化する。N文字

目以降の暗号化には、再びk

₀

から順に使う。

2017.04.19

文字列(平文)と鍵の長さN, およびN個の整数値を受け取ると、

上記の暗号化を行って得られる文字列を出力するプログラム

を考えよう。

Never give up.

Slyjy lpyj xu.

5 7 ₃

改造版シーザー暗号

#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; } }

2017.04.19

for(i=0 ; i<N ; i++) { scanf("%d",key+i); } caesar2(s,N,key); printf("%s",s); return 0; }

鍵が配列

鍵のki番目

の値を使う

intの配列の要

素へのポインタ

を渡す

改造版シーザー暗号を破ってみる

改造前と同様に全通り出力すればよい(?)

N=2 では、26

2

_=676通り

N=3 では、26

3

_{=17,576通り}

これくらいが、人間の目でみてチェックできる限界

※ 平文の長さ ≦ 鍵の長さ のときは、そもそも破れない。

暗号文と鍵の長さ(N)が入力されたとき、可能な平文

を全通り出力するプログラムを考えよう。

2017.04.19

入力値Nに対してN重ループが要る？

26

N

_{通りの鍵がありうる。}



0～25の繰り返しをN重にすれば全通りを数え挙げ

られる(?)



Nは入力値なので、プログラムを書いている時点

では分からない。

→ N重ループのプログラムは書けない

例えば次のようなプログラミング方法がある：

① 0～26

N

_{-1の繰り返しをする}

② 0～25の繰り返しの中で再帰呼出しをする

2017.04.19

改造版シーザー暗号を破ろうとするプログラム①

#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; }

2017.04.19

関数 caesar2 の定義

for(i=0 ; i<pk ; i++) { char cp[MAXLEN]; int j,k=i; for(j=0 ; j<N ; j++) { key[j] = k%26; k /= 26; } caesar2(cp,N,key); printf("%s",cp); } }

s を cp にコピーするコード

xのy乗の

計算

鍵の数え挙げ

i番目の

鍵を作る

改造版シーザー暗号を破ろうとするプログラム②

#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++) { key[n] = i; keygen(N,n+1,key,s); } return; }

2017.04.19

関数 caesar2 の定義

s を cp にコピーするコード

繰り返しの中で

再帰呼出し。

再帰の終端で復号

して表示

MAXKEY(鍵の最大長さ)を6にした理由

26

_{=308,915,776 < 2}

_{=2,147,483,648 < 26}

_{=8,031,810,176}

なので、鍵の総数を 32bitの int で表すと

すると、鍵の長さは最大 6



「改造版シーザー暗号を破ろうとするプログラム①」は、

長さ7以上の鍵に対応していない。



「改造版シーザー暗号を破ろうとするプログラム②」は、

長さ7以上の鍵でも動く。

ただし、何億もの候補を提示されても人間はチェックできないので無意味

2017.04.19

出席確認演習

暗号を破りたいとする。

どんなプログラムがあれば、「人間の目で見て

チェックする」ことの代わりができるだろうか？

周囲の人と議論可。

提出方法：[email protected] 宛にメール

提出期限：今日中

2017.04.19

次回予告

構造体