Caesar(less comfortable)

Caesar暗号を使用してメッセージを暗号化するプログラムを実装します。

$ ./caesar 13
plaintext:  HELLO
ciphertext: URYYB

背景

Caesar (シーザー/カエサル) は、機密メッセージを作る (すなわち、可逆的な方法で隠す)ために、それぞれの文字をずらしていたと考えられています。例えば、AをB、BをC、CをD、…とし、ZをAと書き、HELLOと言うために、シーザーはIFMMPと書いていたかもしれません。

この 「暗号システム」 の秘密はシーザーだけに依存しており、受取人はシーザーが彼の手紙をシフトした文字数 (例:1) という秘密を知っていました。現代の標準では特に安全というわけではありませんが、世界で初めての試みでしたでしょうから、かなり安全です。

暗号化されていないテキストは、一般に平文 (プレーンテキスト) と呼ばれます。暗号化されたテキストは、一般に暗号文と呼ばれます。使用される秘密は鍵と呼ばれます。

ここでは、HELLOを1のキーで暗号化するとIFMMPが生成される仕組みを説明します。

plaintextHELLO
+ key11111
= ciphertextIFMMP

より正式には、Caesarのアルゴリズム (暗号文) は、各文字をk個の位置だけ 「ずらす」ことによってメッセージを暗号化します。もっと正式にいうと、pが平文 (暗号化されていないメッセージ) で、piがpのi番目の文字で、kが秘密鍵 (負でない整数) なら、暗号文cのそれぞれの文字ciは次のように計算されます。

ci = (pi + k) % 26

ここで% 26は 「26で割ったときの剰余」 を意味します。この公式は、暗号を実際よりも複雑に見せるかもしれませんが、アルゴリズムを正確に表現するための簡潔な方法にすぎません。実際、議論のために、A (またはa) を0、B (またはb) を1、…、H (またはh) を7、I (またはi) を8、…、Z (またはz) を25と考えてみましょう。Caesarが、今度は3のキーkを使って、内密に誰かにHiと言いたいとします。そのため、平文pはHiになり、その場合、平文の最初の文字p0はH (または7) になり、2番目の文字p1はi (または8) になります。彼の暗号文の最初の文字c0はしたがってKであり、二番目の文字 c1はLになります。

ここでは、Caesarの暗号を使用してメッセージを暗号化できるcaesarというプログラムを作成します。ユーザはプログラムを実行するときに、コマンドライン引数を指定して、実行時に提供する秘密メッセージ内のキーを決定する必要があります。ユーザのキーが数字であると必ずしも仮定すべきではありません。また、数値の場合は正の整数でなければなりません。

プログラムの動作例をいくつか示します。たとえば、ユーザが1のキーとHELLOというプレーンテキストを入力したとします。

$ ./caesar 1
plaintext:  HELLO
ciphertext: IFMMP

ユーザが13のキーとhello, worldのプレーンテキストを入力すると、プログラムは次のように動作します。

$ ./caesar 13
plaintext:  hello, world
ciphertext: uryyb, jbeyq

カンマもスペースも暗号によって 「シフト」 されていないことに注意してください。英字のみをシフトさせます。

もうひとつ試してみましょう。ユーザが再び13の鍵をもっと複雑な平文で示した場合、プログラムはどのように動作するかを以下に示します。

$ ./caesar 13
plaintext:  be sure to drink your Ovaltine
ciphertext: or fher gb qevax lbhe Binygvar

なぜでしょうか?

元のメッセージの大文字と小文字が保持されていることに注意してください。小文字は小文字のまま、大文字は大文字のままです。

また、ユーザが指示に従わない場合はどうなりますか。

$ ./caesar HELLO
Usage: ./caesar key

ユーザが全く指示に従っていない場合はどうでしょう。

$ ./caesar
Usage: ./caesar key

または…

$ ./caesar 1 2 3
Usage: ./caesar key

試してみましょう

スタッフによるこの問題の実装をテストするには、次のコマンドを実行します。

./caesar key

このサンドボックス内で、keyの代わりに有効な整数を代入します。

仕様

Caesarの暗号を使用してメッセージを暗号化するプログラムcaesarを設計および実装します。

  • caesarというディレクトリにあるcaesar.cというファイルにプログラムを実装します。
  • プログラムは、1つのコマンドライン引数 (負でない整数) を受け入れる必要があります。議論のためにkとしましょう。
  • プログラムをコマンドライン引数なしで、または複数のコマンドライン引数を指定して実行した場合、プログラムはエラーメッセージ (printfで) を出力し、mainから値1 (エラーを示す) をすぐに返します。
  • コマンドライン引数の文字のいずれかが10進数でない場合、プログラムはUsage: ./caesar keyというメッセージを出力し、mainから値1が返されます。
  • kが26以下であると仮定しないでください。プログラムは、2^31 -26より小さいkのすべての非負の整数値に対して機能するはずです。つまり、ユーザがintに適合するには大きすぎるkの値を選択した場合に、プログラムが最終的に壊れてしまうと心配する必要はありません (intはオーバーフローする可能性があることを思い出してください)。ただし、kが26より大きい場合でも、プログラムの入力のアルファベット文字は、プログラムの出力のアルファベット文字のままである必要があります。たとえば、kが27の場合、http://www.asciichart.com/[asciichart.com]によれば、Aは27離れている [ではなく、ZからAに戻るとしてAから27離れた位置にあるBになります。
  • プログラムは (改行なしの) plaintext:を出力し、ユーザに (get_stringを使って) プレーンテキストのstringを要求しなければなりません。
  • プログラムは (改行なしで) ciphertext:を出力しなければなりません。 平文と対応する暗号文が続き、平文中のアルファベット文字がそれぞれkずつ 「ずれて」 して出力されます。アルファベット以外の文字はそのまま出力されます。
  • プログラムは大文字と小文字を保持する必要があります。大文字はずらしても大文字のままである必要があります。小文字はずらしても小文字のままである必要があります。
  • 暗号文を出力した後、改行を出力する必要があります。プログラムはmain0を返して終了するはずです。

どうやって始めますか?この問題に一歩ずつ取り組みましょう。

擬似コード

まず、たとえどのようにコードを実装するか定かでなくても、疑似コードを考えてみてください。疑似コードを書く正しい方法は1つではありませんが、短い英文で十分です。finding Mike Smithで擬似コードを書いたことを思い出してみましょう。疑似コードでは1つ以上の関数、条件、ブール式、ループ、または変数が使用されるでしょう。

ネタバレ

複数の方法がありますが、ここでは1つだけを紹介します。

  1. プログラムが1つのコマンドライン引数で実行されたことを確認します。
  2. 指定された引数を繰り返して、すべての文字が数字であることを確認します。
  3. コマンドライン引数をstringからintに変換します。
  4. 平文を要求します。
  5. 平文の各文字を繰り返します。
    1. 大文字の場合は、大文字を保持したままシフトしてから、シフトした文字を表示します。
    2. 小文字の場合は、小文字を保持したままシフトしてから、シフトした文字を表示します。
    3. どちらでもない場合は、文字をそのまま表示します。
  6. 改行を出力します。

この擬似コードを参考に自分で疑似コードを編集してかまいませんが、これを単にコピー&ペーストするのはやめてください。

コマンドライン引数のカウント

擬似コードが何であれ、追加機能を追加する前に、プログラムが単一のコマンドライン引数で実行されたかどうかをチェックするCコードのみを最初に記述します。

具体的には、caesar.cを次のように変更します。ユーザがコマンドライン引数を1つだけ指定した場合、Successと表示します。コマンドライン引数を指定しなかったり、複数指定したりすると、Usage: ./caesar keyと表示されます。このキーはget_string経由ではなく、実行時にコマンドラインから取得されるため、ユーザに再度プロンプトを表示することはできません。結果のプログラムの動作は次のようになります。

$ ./caesar 20
Success

または

$ ./caesar
Usage: ./caesar key

または

$ ./caesar 1 2 3
Usage: ./caesar key

ヒント

  • makeを使ってプログラムをコンパイルできることを思い出してください。
  • printfで表示できることを思い出してください。
  • argcとargvは、コマンドラインで何が提供されたかについての情報を提供することを思い出してください。
  • プログラム自体の名前(./caesar)はargv[0]にあることを思い出しましょう。

キーへのアクセス

これでプログラムが (願わくば) 指定された入力を受け入れ、次のステップに進みます。

このプログラムでは、技術的には1つのコマンドライン引数 (キー) を提供しますが、実際には整数ではないものを入力するユーザに対して対応する必要があることを思い出してください。

$ ./caesar xyz

ただし、キーの有効性を分析する前に、キーが実際に読めることを確認します。caesar.cをさらに変更して、ユーザがコマンドライン引数を1つだけ指定したかどうかをチェックするだけでなく、それを確認した後、その1つのコマンドライン引数を出力するようにします。たとえば、動作は次のようになります。

$ ./caesar 20
Success
20

ヒント

  • argcとargvは、コマンドラインで何が提供されたかについての情報を提供することを思い出してください。
  • argvは文字列の配列であることを思い出してください。
  • printfでは、プレースホルダとして%sを使用して文字列を出力できることを思い出してください。
  • コンピュータ科学者は0から数えるのが好きだということを思い出しましょう。
  • argv[0]のように角括弧を使ってargvのような配列の個々の要素にアクセスできることを思い出してください。

キーの検証

キーの読み方がわかったので、キーを分析します。caesar.cを変更して、指定されたコマンドライン引数を出力する代わりに、プログラムがそのコマンドライン引数の各文字が10進数 (0、1、2など) であることを確認し、いずれかが10進数でない場合は、Usage: ./caesar keyというメッセージを出力した後で終了するようにします。引数が数字だけで構成されている場合は、その文字列 (argvは文字列の配列であることを思い出してください。たとえそれらの文字列がたまたま数字のように見えたとしてもです) を実際の整数に変換し、printfを使用して%i経由で整数を出力する必要があります。たとえば、動作は次のようになります。

$ ./caesar 20
Success
20

または

$ ./caesar 20x
Usage: ./caesar key

ヒント

  • argvは文字列の配列であることを思い出してください。
  • 一方、文字列は単なる文字の配列であることを思い出してください。
  • string.hヘッダファイルには、文字列を処理する便利な関数がいくつか含まれています。
  • 文字列の長さがわかっていれば、ループを使って文字列の各文字を繰り返し処理できることを思い出してください。
  • ctype.hヘッダファイルには、文字に関する情報を提供する便利な関数がたくさん含まれていることを思い出してください。
  • プログラムが正常に終了しなかったことを示すために、mainから0以外の値を返すことができることを思い出してください。
  • printfで%iをプレースホルダとして使って整数を出力できることを思い出してください。
  • atoi関数は、数値に似た文字列をその数値に変換することを思い出してください。

問題を念入りに調べる

人間としては 「H+1=I」 と言える以上、上記の公式を直感的に理解することは容易です。しかしコンピュータは同じ論理を理解できるのでしょうか?調べてみましょう。ここでは、ユーザが入力したキーを一時的に無視し、代わりにユーザに秘密のメッセージを要求して、そのすべての文字を1だけずらします。

caesar.cの機能を拡張し、キーを検証した後、ユーザに文字列の入力を求め、すべての文字を1ずつシフトして結果を出力するようにします。この時点で、Successを出力するコード行を削除することもできます。つまり、この結果、次のような動作になるでしょう。

$ ./caesar 1
plaintext:  hello
ciphertext: ifmmp

ヒント

  • 平文のすべての文字を繰り返し処理し、文字どおり1を加えてから、それを印刷してみてください。
  • cがchar型の変数である場合、printf(“%c”, c + 1); を実行するとどうなりますか?

あなたの番

今こそ、すべてを1つにまとめるときです。文字を1ずつシフトするのではなく、caesar.cを変更して実際のキー値だけシフトします。そして、文字の大小はそのままにしてください!大文字は大文字のまま、小文字は小文字のまま、アルファベット以外の文字は変更しないでください。

ヒント

  • ZからAへのラップを処理するには、モジュロ (剰余) 演算子%を使用するのが最適です。どうするのでしょうか?
  • 前のセクションで説明した方法を使用してZまたはzを1でラップしようとすると、状況がおかしくなります。
  • このテクニックを使って句読点もラップしようとすると、状況がおかしくなります。
  • ASCIIはすべての印刷可能な文字を数字にマップすることを思い出してください。
  • AのASCII値は65であることを思い出しましょう。一方、aのASCII値は97です。
  • printfを呼び出しても出力がまったく表示されない場合は、0から127までの有効なASCII範囲外の文字を印刷している可能性があります。まず、%cではなく%iを使用して数字として文字を印刷してみて、印刷する値を確認し、有効な文字だけを印刷しようとしていることを確認してください。

ウォークスルー

コードのテスト方法

check50を使用して以下を実行し、コードの正確さを評価してください。ただし、コンパイルとテストは必ず自分で行ってください。

check50 cs50/problems/2021/x/caesar

以下を実行し、style50を使用してコードのスタイルを評価します。

style50 caesar.c

提出方法

次のコマンドを実行し、GitHubのユーザ名とパスワードを入力してログインします。セキュリティのため、パスワードには実際の文字ではなくアスタリスク (*) が表示されます。

submit50 cs50/problems/2021/x/caesar