わさっきhb

大学(教育研究)とか ,親馬鹿とか,和歌山とか,とか,とか.

文字単位のローテーション

シーザー暗号により暗号化された文字列hatteが与えられたとき,その平文は何であるかを求めることから始まります.よく例題に使用されるシーザー暗号では,平文の各文字について,「3文字,後ろ」に変換します.aならd,bならe,…,wならzで,xなら最初に戻ってa,yならb,zならcとなります.ただし今回考えるシーザー暗号の変換方法は,3固定ではなく,「N文字,後ろ」とし,整数値Nを暗号化の鍵とすることにします.
それで,先ほど書いたとおりhatteは暗号文なのですが,ひとまずこれを平文と見なすことにして,「N文字,後ろ」に変換するとどのような暗号文ができるかを,プログラムを作って求めることにします.アルファベットは26文字で,「26文字,後ろ」というのは「何も変換しない」と同じなので,Nはそこで打ち切ります.

/* rotwod1.c */

#include <stdio.h>
#include <ctype.h>

void nextchar(char *s)
{
  char *t;

  for (t = s; *t != '\0'; t++) {
    if (isupper(*t)) {
      *t = (*t - 'A' + 1) % 26 + 'A';
    } else if (islower(*t)) {
      *t = (*t - 'a' + 1) % 26 + 'a';
    }
  }
}

int main(int argc, char *argv[])
{
  char default_str[] = "hatte";
  char *str = default_str;
  int i;

  if (argc > 1) {
    str = argv[1];
  }

  for (i = 0; i < 26; i++) {
    nextchar(str);
    printf("%2d: %s\n", i + 1, str);
  }

  return 0;
}

少しだけプログラムの内容を解説しておきますと,「1文字,後ろ」,「2文字,後ろ」,…と順に求めるときに,元の文字列からではなく,直前に作った文字列に対して操作をします.より正確には,「『N文字,後ろ』の文字列は,『N-1文字,後ろ』にした文字列に対して『1文字,後ろ』にすることで求められる」という,漸化式のような考え方を用いています*1
それと,文字コードはASCIIを前提としています.'A'から'Z'まで,'a'から'z'までが連続した文字コードであるというものです.もしそのような前提を置かない場合には,文字が,対象とするアルファベットの何番目になるかを求める関数と,その逆関数を定義して呼び出せばよいでしょう.
実行結果は以下のとおり.

 1: ibuuf
 2: jcvvg
 3: kdwwh
 4: lexxi
 5: mfyyj
 6: ngzzk
 7: ohaal
 8: pibbm
 9: qjccn
10: rkddo
11: sleep
12: tmffq
13: unggr
14: vohhs
15: wpiit
16: xqjju
17: yrkkv
18: zsllw
19: atmmx
20: bunny
21: cvooz
22: dwppa
23: exqqb
24: fyrrc
25: gzssd
26: hatte

これを踏まえて,次に買い得解読です.もとの文字列だけでなく,何文字,後ろにしたかのNも合わせて求めることにします.そのために,「N文字,前」を求めます.後ろを前にするだけなので,単純に書き換えると,こうなります.

/* rotwod2-bad.c */

#include <stdio.h>
#include <ctype.h>

void prevchar(char *s)
{
  char *t;

  for (t = s; *t != '\0'; t++) {
    if (isupper(*t)) {
      *t = (*t - 'A' - 1) % 26 + 'A';
    } else if (islower(*t)) {
      *t = (*t - 'a' - 1) % 26 + 'a';
    }
  }
}

int main(int argc, char *argv[])
{
  char default_str[] = "hatte";
  char *str = default_str;
  int i;

  if (argc > 1) {
    str = argv[1];
  }

  for (i = 0; i < 26; i++) {
    prevchar(str);
    printf("%2d: %s\n", i + 1, str);
  }

  return 0;
}

実行結果ですが,残念ながら,うまくいっていません.

 1: g`ssd
 2: f`rrc
 3: e`qqb
 4: d`ppa
 5: c`oo`
 6: b`nn`
 7: a`mm`
 8: ``ll`
 9: ``kk`
10: ``jj`
11: ``ii`
12: ``hh`
13: ``gg`
14: ``ff`
15: ``ee`
16: ``dd`
17: ``cc`
18: ``bb`
19: ``aa`
20: `````
21: `````
22: `````
23: `````
24: `````
25: `````
26: `````

原因は,'a'の一つ前が,'z'ではなく'`'になっていることです.
ASCIIのコードで'a'が97,'`'は96です*2.「*t = (*t - 'a' - 1) % 26 + 'a';」という式を評価する前の *t の値が 'a' のとき,評価結果が '`' となっていまして,この中の「(*t - 'a' - 1) % 26」が,-1 になってしまうのが,期待通り動作しなかった理由と言えます.
修正版です.

/* rotwod2.c */

#include <stdio.h>
#include <ctype.h>

void prevchar(char *s)
{
  char *t;

  for (t = s; *t != '\0'; t++) {
    if (isupper(*t)) {
      *t = (*t - 'A' - 1 + 26) % 26 + 'A';
    } else if (islower(*t)) {
      *t = (*t - 'a' - 1 + 26) % 26 + 'a';
    }
  }
}

int main(int argc, char *argv[])
{
  char default_str[] = "hatte";
  char *str = default_str;
  int i;

  if (argc > 1) {
    str = argv[1];
  }

  for (i = 0; i < 26; i++) {
    prevchar(str);
    printf("%2d: %s\n", i + 1, str);
  }

  return 0;
}

「- 1 + 26」は「+ 25」に簡約できますが,アルファベットが26文字でない状況にも再利用しやすいよう,計算しない状態にしておきます.
それで結果です.

 1: gzssd
 2: fyrrc
 3: exqqb
 4: dwppa
 5: cvooz
 6: bunny
 7: atmmx
 8: zsllw
 9: yrkkv
10: xqjju
11: wpiit
12: vohhs
13: unggr
14: tmffq
15: sleep
16: rkddo
17: qjccn
18: pibbm
19: ohaal
20: ngzzk
21: mfyyj
22: lexxi
23: kdwwh
24: jcvvg
25: ibuuf
26: hatte

結果は,文字列の順番を見ると,最初の「暗号化」の逆順になっていることが分かります.しかし先頭の数字が違います../rotword2を実行することで,hatteの解読結果の候補として,6文字,前にした「bunny」と,15文字,前にした「sleep」の2種類が考えられます.一意に解読できない,ずるい暗号文なのでした.
除数が正の整数で,被除数が正に限らない整数というときでも,余りを0以上除数未満の範囲で求める*3ような「俺mod」関数を,書いてみました.

int my_mod(int num, int den)
{
  return num >= 0
    ? num % den
    : (den - (den - num) % den) % den;
}

最後の「% den」は,それまでの式の結果がdenのとき(「(den - num) % den」が0のとき)に限り0,そうでなければそのままという処理をしますので,剰余演算を減らしたければ,いったんその被除数を変数に格納した上で,条件分岐すればよいでしょう.
「:」以降の式がやたらと複雑ですが,numがINT_MINやINT_MAX,それらに近い値であっても,オーバーフローすることなく求められるようにしているためで,実用上は(今回の,文字のローテーションにおいても),こんな三項演算子を使わずとも,「(num + den) % den」で十分となるケースが多いでしょう.
ともあれこれで,上のrotword2.cの「*t = (*t - 'a' - 1 + 26) % 26 + 'a';」を「*t = my_mod(*t - 'a' - 1, 26) + 'a';」に,'A'についても同様に置き換えると,同じ出力になります.

*1:もし「N文字,後ろ」にする文字列を求める関数を定義してから,1以上26以下のそれぞれで(for文で回して)その関数を呼び出すとすると,変換元の文字列を保存するとかコピーするとかいった処理が必要になります.なお,プログラムでは,コマンドライン引数があればその最初のものを処理対象としていますが,argvが指し示す文字列を書き換えてよいことは,規格で保証されています.

*2:asciiというコマンドで,文字コード一覧が出ます.Cygwinでも利用可能です.DebianUbuntuでは,あらかじめapt-get install asciiとしておきます.

*3:C89までは,「%」の評価結果がそのようになるような処理系を認めていましたが,C99では不可で,-1/2は必ず0,-1%2は-1です.http://seclan.dll.jp/c99d/c99d05.htm#dt19990607