初心者用の簡単な暗号解析プログラム

[じゃすと]

先週からC言語を学び始めた じゃすと と申します。初めての投稿となるので、至らない点がありましたらご指摘ください。

まず、独習Cという参考書に乗っていた問題で、

「ユーザーから文字列を受け取って暗号化するプログラムを作成せよ。
このとき暗号化では、文字列の両端の文字を左から始めて交互に取り出し、文字列の真ん中に達した時に終わるようにする。
例えば Hi there という文字列は Heir eth となる」

という問題があって、この問題に関しては一応答えをちらちらと見ながらも理解はしました。

ここからが本題なのですが、「 入力した文字列→暗号化→元の入力した文字列 」　と変換できるプログラムも考えてみようと思いました（これはあくまで興味本位なのですが）
要は暗号化した文字列(Heir eth) を元の文字列(Hi there) に戻すプログラムのことです。
しかし、考えてもつまずいてしまったので質問させていただきます。

私が考えた暗号化文字列の復元の手順としては、
１、暗号化した文字列を配列に格納(例えばchar 型のstrという変数に格納するとする)
２、格納した配列のstr[0], str[2], str[4], str[6], str[7], str[5], str[3], str[1] という順に読み込みようにすれば、元の文字列になるのでは。

と考えたのですが、１つめの段階でつまずいてしまいました。
暗号化プログラムは以下に示します。

プログラムでは配列のある部分を参照して文字で表示、というのをつなげて文字列にしているので、うまく出力を配列に格納できればいいのになーと思っているのですが、なかなかできず。

ご教授お願いいたします。

コード:

#include<stdio.h>
#include<string.h>

int main(void)
{
	char word[80];
	int i, j;

	printf("Input word: ");
	gets(word);
	
	i=0, j=strlen(word)-1;
	while(i<=j){
		if(i<j) printf("%c%c", word[i], word[j]);
		else printf("%c", word[i]);
		i++; j--;
	}
	printf("\n");

	return 0;
}

・環境
OS: windows 7 32bit
コンパイラ: Borland C++ Compiler 5.5

[non]

考え方はそれでいいでしょう。
で、
１、暗号化した文字列を配列に格納(例えばchar 型のstrという変数に格納するとする)
が、できないというのはどこがわからないのでしょうか？

やり方としては
１　配列strを用意する。
２　strは前から順番に格納するので、どこに格納するかをカウントする変数例えばkを用意して最初はk=0
３　printfで現在文字を出力している命令の代わりにstrの配列に1文字ずつ格納する。　例えば　str[k]=word
４　1文字格納したらkをカウントアップする。
５　whileから抜けた後、正しく格納されたか表示する。例えば　puts(str)

[じゃすと]

やり方としては
１　配列strを用意する。
２　strは前から順番に格納するので、どこに格納するかをカウントする変数例えばkを用意して最初はk=0
３　printfで現在文字を出力している命令の代わりにstrの配列に1文字ずつ格納する。　例えば　str[k]=word
４　1文字格納したらkをカウントアップする。
５　whileから抜けた後、正しく格納されたか表示する。例えば　puts(str)

一応、悪戦苦闘しながらも書いてみました。

コード:

#include<stdio.h>
#include<string.h>

int main(void)
{
	char word[80], str[80];
	int i, j, k;

	printf("Input word: ");
	gets(word);
	
	i=0, k=0, j=strlen(word)-1;
	while(i<=j){
		if(i<j)	{
			str[k] = word[i];
			str[k+1]=word[j];
			printf("%c%c", word[i], word[j]);
		}
		else {
			str[k] = word[i];
			printf("%c", word[i]);
		}
		i++;
		j--;
		k=k+2;
	}
	printf("\n");
	puts(str);
	return 0;
}

一応、ちゃんと格納できているのか確認しやすいようにprintfはそのままにしてあります。しかし、この文だとおそらくkがNULL文字まで格納しているせいか、出力結果の最後にいらない文字まで付随していまいます。

k=k+2としているので、そこでkがNULL文字に達したのか判別すればいいのか？そもそもkがstrlen(word)-1 に達したのか判別すればいいのか？と分かりません。

ご指摘お願いいたします。

[YuO]

この手の物は，最初はループを分けたり，バッファ自体も分けたりして考えた方が考えやすいと思います。

まず，暗号化について。

1. 平文をwordに入力する
2. 暗号文のバッファstrを用意する
3. 配列の前半部分をコピーしていくためのバッファfront_bufferを用意する
4. 配列の後半部分をコピーしていくためのバッファlatter_bufferを用意する
5. 入力文字列長length = strlen(word)を求める
6. 配列の前半部分をコピーする長さlength_front = (length + 1) / 2を求める
7. 配列の後半部分をコピーする長さlength_latter = length - length_frontを求める
8. 範囲[0, length_front)のiについてwordをfront_bufferにコピーする <A>
9. front_buffer[length_front]に\0を代入しておく
10. ここでfront_bufferを出力してみてもよい
11. 範囲[0, length_latter)のiについてword[i + length_front]をlatter_buffer[length_latter - i - 1]にコピーする <B>
12. latter_buffer[length_latter]に\0を代入しておく
13. ここでlatter_bufferを出力してみてもよい
14. 範囲[0, length_front)のiについてfront_bufferをstr[i * 2]にコピーする <C>
15. 範囲[0, length_latter)のiについてlatter_bufferをstr[i * 2 + 1]にコピーする <D>
16. str[length]に\0を代入する
17. strを出力する

効率は悪いですが，これでstrがちゃんと完成します。

次に復号について。

1. 暗号文をstrに入力する
2. 平文のバッファwordを用意する
3. 配列の前半部分をコピーしていくためのバッファfront_bufferを用意する
4. 配列の後半部分をコピーしていくためのバッファlatter_bufferを用意する
5. 入力文字列長length = strlen(str)を求める
6. 配列の前半部分をコピーする長さlength_front = (length + 1) / 2を求める
7. 配列の後半部分をコピーする長さlength_latter = length - length_frontを求める
8. 範囲[0, length_front)のiについてstr[i * 2]をfront_bufferにコピーする <C>
9. front_buffer[length_front]に\0を代入しておく
10. ここでfront_bufferを出力してみてもよい
11. 範囲[0, length_latter)のiについてstr[i * 2 + 1]をlatter_bufferにコピーする <D>
12. latter_buffer[length_latter]に\0を代入しておく
13. ここでlatter_bufferを出力してみてもよい
14. 範囲[0, length_front)のiについてfront_bufferをwordにコピーする <A>
15. 範囲[0, length_latter)のiについてlatter_bufferをword[length - i - 1]にコピーする <B>
16. word[length]に\0を代入する
17. wordを出力する

となります。暗号化と比較すれば，<A>, <B>, <C>, <D>が対応していることがわかると思います。
# front_buffer, latter_bufferが暗号化・復号で同じになります。

次に，front_bufferとlatter_bufferを削除することを考えます。
<A>と<C>，<B>と<D>をまとめればこれらの中間バッファが削除できます。
まずは暗号化について。

• 前半部分について，
  • <A>よりwordはfront_buffer[i]
  • <C>よりfront_buffer[i]はstr[i * 2]
  よってword[i]はstr[i * 2]になる
• 後半部分について，
  • <B>よりword[i + length_front]はlatter_buffer[length_latter - i - 1]
  • <D>よりlatter_buffer[length_latter - i - 1]はstr[(length_latter - i - 1) * 2 + 1]
  よって，word[i + length_front]はstr[(length_latter - i - 1) * 2 + 1]になる

復号については，上記の結論部分をstr→wordの向きに読み替えます。
# 後半部分については復号の<D><B>から出した方が綺麗に結論付けられますが。


実際には平文中の位置と平文の長さから暗号文中の位置が計算できます。
また，暗号文中の位置と暗号文の長さから平文中の位置も計算できます。

• 平文および暗号文の長さをNとする
• 0 <= i && i < Nとする
• i < (N + 1) / 2の時，平文中の位置がiの文字は暗号文中ではi * 2の位置にくる <E>
• (N + 1) / 2 <= iの時，平文中の位置がiの文字は暗号文中では(N - i) * 2 - 1の位置にくる <F>
• iが偶数の時，暗号文中の位置がiの文字は平文中ではi / 2の位置にくる <E>
• iが奇数の時，暗号文中の位置がiの文字は平文中ではN - (i + 1) / 2の位置にくる <F>

これを使えば，複数のバッファは不要です。これも，<E>と<F>がそれぞれ対応しているのがわかります。

• 暗号化時の偶奇は必ず復号部分の条件に相当する
• 復号後の位置の計算式のiに暗号化時の位置の計算式を代入するとiになる

► スポイラーを表示

サンプル。あくまでサンプルなのでエラーやセキュリティには一切気を配っていません。

コード:

#include    <stdio.h>
#include    <string.h>

#define MAX_LENGTH 128

/* 最初の方法での暗号化 */
void encode1 (const char * input, char * output)
{
    char front_buffer[MAX_LENGTH]; /* (3) */
    char latter_buffer[MAX_LENGTH]; /* (4) */
    int length, length_front, length_latter, i;

    printf("encode1 : input = \"%s\"\n", input);

    length = strlen(input); /* (5) */
    length_front = (length + 1) / 2; /* (6) */
    length_latter = length - length_front; /* (7) */

    printf("encode1 : length = %i / length_front = %i / length_latter = %i\n", length, length_front, length_latter);

    /* (8) <A> */
    for (i = 0; i < length_front; ++i)
    {
        front_buffer[i] = input[i];
    }
    front_buffer[length_front] = 0; /* (9) */
    printf("encode1 : front_buffer = \"%s\"\n", front_buffer); /* (10) */

    /* (11) <B> */
    for (i = 0; i < length_latter; ++i)
    {
        latter_buffer[length_latter - i - 1] = input[i + length_front];
    }
    latter_buffer[length_latter] = 0; /* (12) */
    printf("encode1 : latter_buffer = \"%s\"\n", latter_buffer); /* (13) */

    /* (14) <C> */
    for (i = 0; i < length_front; ++i)
    {
        output[i * 2] = front_buffer[i];
    }
    /* (15) <D> */
    for (i = 0; i < length_latter; ++i)
    {
        output[i * 2 + 1] = latter_buffer[i];
    }
    output[length] = 0; /* (16) */
    printf("encode1 : output = \"%s\"\n", output); /* (17) */
}

/* 最初の方法での復号 */
void decode1 (const char * input, char * output)
{
    char front_buffer[MAX_LENGTH]; /* (3) */
    char latter_buffer[MAX_LENGTH]; /* (4) */
    int length, length_front, length_latter, i;

    printf("decode1 : input = \"%s\"\n", input);

    length = strlen(input); /* (5) */
    length_front = (length + 1) / 2; /* (6) */
    length_latter = length - length_front; /* (7) */

    printf("decode1 : length = %i / length_front = %i / length_latter = %i\n", length, length_front, length_latter);

    /* (8) <C> */
    for (i = 0; i < length_front; ++i)
    {
        front_buffer[i] = input[i * 2];
    }
    front_buffer[length_front] = 0; /* (9) */
    printf("decode1 : front_buffer = \"%s\"\n", front_buffer); /* (10) */

    /* (11) <D> */
    for (i = 0; i < length_latter; ++i)
    {
        latter_buffer[i] = input[i * 2 + 1];
    }
    latter_buffer[length_latter] = 0; /* (12) */
    printf("decode1 : latter_buffer = \"%s\"\n", latter_buffer); /* (13) */

    /* (14) */
    for (i = 0; i < length_front; ++i)
    {
        output[i] = front_buffer[i];
    }
    /* (15) */
    for (i = 0; i < length_latter; ++i)
    {
        output[length - i - 1] = latter_buffer[i];
    }
    output[length] = 0; /* (16) */
    printf("decode1 : output = \"%s\"\n", output); /* (17) */
}

/* 2番目の方法で暗号化 */
void encode2 (const char * input, char * output)
{
    int length, length_front, length_latter, i;

    printf("encode2 : input = \"%s\"\n", input);

    length = strlen(input);
    length_front = (length + 1) / 2;
    length_latter = length - length_front;

    printf("encode2 : length = %i / length_front = %i / length_latter = %i\n", length, length_front, length_latter);

    /* 前半部分 */
    for (i = 0; i < length_front; ++i)
    {
        output[i * 2] = input[i];
    }
    /* 後半部分 */
    for (i = 0; i < length_latter; ++i)
    {
        output[(length_latter - i - 1) * 2 + 1] = input[i + length_front];
    }
    output[length] = 0;
    printf("encode2 : output = \"%s\"\n", output);
}

/* 2番目の方法で復号 */
void decode2 (const char * input, char * output)
{
    int length, length_front, length_latter, i;

    printf("decode2 : input = \"%s\"\n", input);

    length = strlen(input);
    length_front = (length + 1) / 2;
    length_latter = length - length_front;

    printf("decode2 : length = %i / length_front = %i / length_latter = %i\n", length, length_front, length_latter);

    /* 前半部分 */
    for (i = 0; i < length_front; ++i)
    {
        output[i] = input[i * 2];
    }
    /* 後半部分 */
    for (i = 0; i < length_latter; ++i)
    {
        output[length - i - 1] = input[i * 2 + 1]; /* 復号<D><B>から導出した式 */
    }
    output[length] = 0;
    printf("decode2 : output = \"%s\"\n", output);
}

/* 最後の方法で暗号化 */
void encode3 (const char * input, char * output)
{
    int length = strlen(input), i;

    printf("encode3 : input = \"%s\"\n", input);
    /* 前半部分 */
    for (i = 0; i < (length + 1) / 2; ++i)
    {
        output[i * 2] = input[i];
    }
    /* 後半部分 */
    for (; i < length; ++i)
    {
        output[(length - i) * 2 - 1] = input[i];
    }
    output[length] = 0;
    printf("encode3 : output = \"%s\"\n", output);
}

/* 最後の方法で復号 */
void decode3 (const char * input, char * output)
{
    int length = strlen(input), i;

    printf("encode3 : input = \"%s\"\n", input);
    for (i = 0; i < length; ++i)
    {
        if (i % 2 == 0)
        {
            output[i / 2] = input[i]; /* 前半部分 */
        }
        else
        {
            output[length - (i + 1) / 2] = input[i]; /* 後半部分 */
        }
    }
    printf("decode3 : output = \"%s\"\n", output);
}

int main (void)
{
    char input_word[MAX_LENGTH];
    char encoded[MAX_LENGTH];
    char decoded[MAX_LENGTH];

    while (gets(input_word) != NULL)
    {
        encode1(input_word, encoded);
        decode1(encoded, decoded);
        puts("");
        encode2(input_word, encoded);
        decode2(encoded, decoded);
        puts("");
        encode3(input_word, encoded);
        decode3(encoded, decoded);
        puts("");
        puts("");
    }

    return 0;
}

[じゃすと]

この手の物は，最初はループを分けたり，バッファ自体も分けたりして考えた方が考えやすいと思います。

1. 暗号文をstrに入力する
2. 平文のバッファwordを用意する
3. 配列の前半部分をコピーしていくためのバッファfront_bufferを用意する
4. 配列の後半部分をコピーしていくためのバッファlatter_bufferを用意する
5. 入力文字列長length = strlen(str)を求める
6. 配列の前半部分をコピーする長さlength_front = (length + 1) / 2を求める
7. 配列の後半部分をコピーする長さlength_latter = length - length_frontを求める
8. 範囲[0, length_front)のiについてstr[i * 2]をfront_bufferにコピーする <C>
9. front_buffer[length_front]に\0を代入しておく
10. ここでfront_bufferを出力してみてもよい
11. 範囲[0, length_latter)のiについてstr[i * 2 + 1]をlatter_bufferにコピーする <D>
12. latter_buffer[length_latter]に\0を代入しておく
13. ここでlatter_bufferを出力してみてもよい
14. 範囲[0, length_front)のiについてfront_bufferをwordにコピーする <A>
15. 範囲[0, length_latter)のiについてlatter_bufferをword[length - i - 1]にコピーする <B>
16. word[length]に\0を代入する
17. wordを出力する

となります。暗号化と比較すれば，<A>, <B>, <C>, <D>が対応していることがわかると思います。
# front_buffer, latter_bufferが暗号化・復号で同じになります。

暗号化等の方針、プログラムまで書いてくださってありがとうございます。
しかし、まだまだC言語を始めて1週間程度ですので、関数であったりポインタであったりと、まだまだ分かっていないところが多々あります。
将来的にはこのようなプログラムをさらさらーと書けるようになれればいいのですが、私にはまだ基礎的な点が足りていないため、今回は参考のみに留まらせていただきます。
それにしても、プログラムの方針がなかなかまとまらない私にとっては、その方針を文章化されるだけでもけっこうな驚きでした。

[七篠真名]

NULL文字まで格納しているというか、NULL文字がないからputs(str);がうまく機能してないのではないでしょうか？
Ｃだと文字列の終わりをNULL文字で判断しているので、NULL文字が出てくるまで表示してしまいます。
つまり現状だとstrの文字列の最後の位置が分からなくてうまく表示されないので、明示的にNULL文字を入力すればいいと思います。
王道なやり方がどうかはわかりませんが、自分のところでは次のようにしてうまくいったと思います。（最後の部分だけ抜粋）
まあ配列にはうまく格納されていると思うので、２番はこのままでも問題なくできると思いますよ。

コード:

	printf("\n");
	str[strlen(word)] = NULL;	/* この行を追加 */
	puts(str);

[じゃすと]

みなさんのご指摘を受け、プログラムとしては汚いながらもなんとか思い通りの動作をさせることができました。ご指摘いただいた皆さん、本当にありがとうございました。
またつまずいたときに質問させていただきます。

コード:

#include<stdio.h>
#include<string.h>

int main(void)
{
	char input[80], code[80], front_buffer[80], rear_buffer[80];
	int i, j, k, length, length_front, length_rear;

	printf("Input word: ");
	gets(input);

	length = strlen(input);
	length_front = (length+1)/2;
	length_rear = length - length_front;

	printf("length=%d length_front=%d length_rear=%d\n", length, length_front, length_rear);

	/* 暗号化 */
	i = 0, k = 0, j = strlen(input)-1;
	while(i<=j){
		if(i<j)	{
			code[k] = input[i];
			code[k+1] = input[j];
		}
		else code[k] = input[i];

		i++;
		j--;
		k=k+2;
	}

	printf("\n");
	code[strlen(input)] = NULL;
	printf("code = %s\n", code);

	/* 複合化  */

	for(i=0;i<length_front;i++){
		front_buffer[i] = code[i*2];
	}
	front_buffer[length_front] = NULL;

	printf("   front_buffer = %s\n", front_buffer);
	
	for(i=0;i<length_rear;i++){
		rear_buffer[length_rear-i-1] = code[i*2+1];
	}	

	rear_buffer[length_rear] = NULL;

	printf("   rear_buffer = %s\n", rear_buffer);

	strcat(front_buffer, rear_buffer); 

	printf("decode = %s", front_buffer);
	
	return 0;
}

[YuO]

細かいことですが，NULLはポインタに対してのみ使うようにしましょう。
'\0'の代わりに使えなくはないですが，NULLは「空ポインタ定数」を意味するのであって「ナル文字」ではないです。

[じゃすと]

細かいことですが，NULLはポインタに対してのみ使うようにしましょう。
'\0'の代わりに使えなくはないですが，NULLは「空ポインタ定数」を意味するのであって「ナル文字」ではないです。

そうなんですね。まだまだしっかりとした知識がないためそのようなご指摘はありがたいです。
わざわざありがとうございました。