DMM.comの、一番深くておもしろいトコロ。

古典的暗号化アルゴリズムをTypeScriptで書いてみる

古典的暗号化アルゴリズムをTypeScriptで書いてみる

  • このエントリーをはてなブックマークに追加

はじめに

この記事は、DMMグループAdvent Calendar 2021の9日目の記事です。合同会社EXNOAにてDMM GAMESのプラットフォーム開発をしている石橋(@usagi-f)が担当します。

プログラミング中に暗号化アルゴリズムを利用しようと考えたとき、ふと「暗号化」とは何なのか、そもそも理解が浅いように感じていました。そこで現代暗号の先祖であるシンプルな古典暗号を例にとって、プログラミングコードに起こしつつ根本的な仕組みと考え方を追ってみます。

現在私がメインに使っているプログラミング時の言語はTypeScriptなので、今回はそれを利用して型の定義にも着目してみます。実際に業務としてつくったコードではありませんが、古典暗号の代表例であるシーザー暗号を題材にして実装を書いてみました。

暗号化の定義と暗号の仕組み

暗号化とは「特定の情報を特定の人のみが解読できるように、一定のルールのもと無意味な情報に置き換えること」と定義できるかと思います。

この一定のルールが「アルゴリズム」となり、置き換え前の情報を「平文(Plain Text)」、置き換え後の情報を「暗号文(Cipher Text)」と呼びます。また、平文を暗号文に変えることを「暗号化(Encryption)」、暗号文を平文に戻すことを「複合(Decryption)」と表現できます。

現代で暗号化といえばコンピューターにおける情報処理技術(ビット演算)が真っ先に思いつきそうです。しかし、これらの定義は遥か昔から既にあり、古くは文字に対して暗号化を施してメッセージのやり取りに機密性を持たせることが行われてきました。このような手法は外交や軍事に対して利用されてきた歴史がありますが、コンピューターの登場やインターネットの発展によって暗号化に求められる要求が高くなっていき、現代の高度な暗号化技術が培われてきました。

暗号のアルゴリズムは、平文に対して「転置(文字の位置を入れ替える)」や「換字(文字を他の文字に入れ替える)」といったことを「鍵」を組み合わせて行うことで、暗号文へ変換します。

ここまでをおさらいすると、暗号の仕組みは次のように表現できます。

C = E(P, K)
  • 暗号文:C(Cipher)
  • アルゴリズム:E(Encryption)
  • 平文:P(Plain)
  • 鍵:K(Key)

シーザー暗号とは

ja.wikipedia.org

シーザー暗号とは代表的な古典暗号の一つです。古代ローマのユリウス・カエサル(英語読みするとカエサル→シーザーとなる)が利用していたことが由来になっています。シーザー暗号は「各文字をアルファベット順で3桁後ろにずらす(シフトする)」という非常に簡単な仕組みで出来ています。(3桁であることは必須ではなく、常に固定値をシフトすることが重要なポイント)

つまり「換字」が行われるタイプの暗号ということになります。

例えば平文が「S」だった場合は、アルファベット順で3つ後ろである「V」に変換されます。このような入れ替えを1つ1つの文字に対して順番に実行していきます。

つまり、平文が「POKEMON」だったら「SRNHPRQ」という文字列にすることができます。

型定義

それではさっそくシーザー暗号をTypeScriptを使って関数として実装してみます。

TypeScriptがJavaScriptと違う大きな要素のひとつとして、型定義が出来ることがあります。まずはシーザー暗号の仕様を型で表現してみましょう。

まずインターフェイスの入力値と出力値として「平文」と「暗号文」を定義します。どちらもアルファベット文字列を想定しているため、string型を指定します。

type Plain = string;
type Cipher = string;

次に、「暗号化」と「複合」の関数を定義します。

暗号化は平文を引数に取り、暗号文を返します。反対に、複合は暗号文を引数に取り、平文を返すことになります。

平文と暗号文は既にTypeScriptで型を宣言しているので、それを参照するように記述できます。

type Encrypt = (p: Plain) => Cipher;
type Decrypt = (c: Cipher) => Plain;

最後に、シーザー暗号は暗号化アルゴリズムとして「固定の桁数を後ろへシフトする」という特徴を持っているので、この処理も型で表現してみましょう。

このシフト処理は暗号化・複合の両方において同じ処理が適用されなければならないため、平文と暗号文の両方が渡される可能性を元から含んでいます。そこで引数と返り値にはUnion型を利用して、PlainとCipherを指定してみます。

さらに、シーザー暗号は桁数に決まりはないが常に固定値をシフトするものなので、鍵もnumber型として引数でもらうようにしてみます。

type Shift = (text: Plain | Cipher, key: number) => Plain | Cipher;

関数の作成

型定義ができたので、これに準拠するように関数を作っていきましょう!

まず、シーザー暗号の鍵は常に固定であることを表すため、代入不可能なconstを利用して変数定義を行います。*1

const caesarKey = 3;

そして暗号化関数と複合関数を考えてみましょう。

これまでの定義に準拠すると次のように表すことができるはずです。

const encrypt: Encrypt = (p) => shift(p, caesarKey);
const decrypt: Decrypt = (c) => shift(c, -Math.abs(caesarKey));

どちらの関数も受け取った入力値を、鍵とともに共通したshift関数に渡しています。

複合の場合は「暗号化とは逆方向へシフトすれば良い」ということになるため、caesarKeyを負数へ変換しています。

(負数変換はいくつか手法がありますが、今回はMath.absで絶対値を取得してからマイナス記号を付与する方式をとってみました)

次に一番重要なシフト処理の中身を実装してみましょう。

一文字ずつ変換処理を実施するので、ここでは配列を利用しようと思います。

const shift: Shift = (text) => {
  const splitted = text.split('');
  return splitted.map((char) => {
    // shift処理
  }).join('');
};

実際のシフト処理にはUnicodeのコードポイントを活用します。

TypeScript(JavaScript)では、String.prototype.charCodeAtでコードポイントを整数で取得し、String.fromCharCodeでその整数を文字列に変換できます。

次のようなコードで、A = 65、B = 66であることが確認できます。これを利用してアルファベットのシフト処理を再現してみようと思います。

"A".charCodeAt(0); // -> 65
String.fromCharCode(65); // -> 'A'

"B".charCodeAt(0); // -> 66
String.fromCharCode(66); // -> 'B'

コードポイントはアルファベット以外の文字列も存在するため、これを考慮しなければいけません。90は「Z」になりますが、91以降は記号が割り当てられています。

「Z」をオーバーした場合は、ループするように再度「A」に戻る必要がありますね。

String.fromCharCode(90); // -> 'Z'
String.fromCharCode(91); // -> '['
String.fromCharCode(92); // -> '\'

そこで実際に書いたコードはこんな感じになりました。

const quantity = (char.charCodeAt(0) - 65 + key) % 26;
const shifted = Math.sign(quantity) >= 0 ? quantity : quantity + 26;
String.fromCharCode(shifted + 65);

まずは基準点をもとに平文がどう変化するのか(移動量 = quantity)を決めます。

「A」が65であることを利用して、平文がAから何個先にあるアルファベットなのかを特定したのちに、key数分シフトさせます。26で割った余りの数を求めることでアルファベットの総数をオーバーした場合でも基準点である「A」から数えるようにしています。

quantityはマイナスになることがあるのでMath.signで判定を行い、アルファベット総数分を移動させることでシフト後の位置が確定できました。

最後に「A」のコードポイントを戻しつつ変換を行います。

平文を考慮して少しだけ入力値に対する変換処理を挟んでみました。これでshift関数は完成です。

const shift: Shift = (text, key) => {
  const normalized = text.replace(/\s+/g, ''); // 空白文字のトリミング
  const uppercase = normalized.toUpperCase(); // 大文字に統一
  const splitted = uppercase.split('');
  return splitted.map((char) => {
    const quantity = (char.charCodeAt(0) - 65 + key) % 26;
    const shifted = Math.sign(quantity) >= 0 ? quantity : quantity + 26;
    return String.fromCharCode(shifted + 65);
  }).join('');
};

実際に実行してみると、シーザー暗号の変換処理が成された値が取得できることが確認できました!

encrypt('POKEMON'); // -> 'SRNHPRQ'
decrypt('SRNHPRQ'); // -> 'POKEMON'

encrypt('My name is Taro'); // -> 'PBQDPHLVWDUR'

さいごに

シーザー暗号という古典暗号を題材にして、非常に簡単な暗号処理をなるべく丁寧にコードベースで追いかけてみました!

今回はシフト桁数を鍵として実装の内部にもたせて再現をしてみましたが、古典暗号はアルゴリズムが簡易的であることもあり、仕組みがバレてしまうと推測が簡単にできる非常に脆弱なものです。

それに対して現代暗号はいくつもの暗号攻撃モデルに対応するために、アルゴリズムは公開しつつも秘匿するべき情報を鍵側に集約するという方法をとっています。(参照:ケルクホフスの原理

ja.wikipedia.org

こういった暗号化技術の発展によって現在の技術革新が達成できたと思うと、1エンジニアとして尊敬の念に堪えませんね!


この記事を作るにあたって参考にさせていただいた書籍

book.mynavi.jp

*1:※ 本記事ではシーザー暗号の再現が趣旨なので、便宜上「caesarKeyは正の整数のみが指定できる」と仮定させて頂きます。本来入力値として数値を取るとき、JavaScriptでは数値型に曖昧な点も多いため負数や小数点などを考慮した判定処理を行ったり、TypeScriptによって厳密な型定義を行ってタイプエラーを起こさせるなどの実践的な対処が必要になります。