ヒル暗号をC++で実装する方法：暗号化と復号の仕組みをサンプルコード付きで解説

ヒル暗号（Hill Cipher）は、線形代数を基礎とする多表字換暗号（polygraphic substitution cipher）の一種で、暗号理論における古典的な手法のひとつです。複数の文字をブロックとしてまとめて変換するため、単純な換字暗号よりも高い安全性を持ちます。

暗号化：鍵文字列と平文（メッセージ）をそれぞれ行列形式で表現し、両者を乗算した結果に対して mod 26 を適用することで暗号文を生成します。後から復号を行うためには、鍵行列が逆行列を持つことが前提条件となります。

復号：暗号化に使用した鍵行列の逆行列を暗号文行列に乗算し、mod 26 を計算することで元のメッセージを復元します。

なお、mod 26 を用いるのは、アルファベットの大文字 A〜Z の26文字に対応させるためです。また、n×n の鍵行列を使うことで n 文字ずつをひとつのブロックとして暗号化でき、以下の例では 3×3 行列によって 3 文字単位で処理を行います。

具体例

鍵行列

1 0 1
2 4 0
3 5 6

メッセージ「ABC」を行列形式で表すと、次のようになります。

0
1
2

暗号化の計算

上記の2つの行列を乗算すると、次の結果が得られます。

2
4
17

これが暗号文「CER」に対応します。

復号の計算

鍵行列の逆行列は以下の通りです。

1.09091 0.227273 -0.181818
-0.545455 0.136364 0.0909091
-0.0909091 -0.227273 0.181818

この逆行列を暗号文行列に乗算すると、

0
1
2

となり、元のメッセージ「ABC」が正しく復元されていることが確認できます。

以下では、この一連の処理を実装したC++プログラムを紹介します。

アルゴリズム

開始
関数 getKeyMatrix()
　　i = 0 ～ 2 について
　　　　j = 0 ～ 2 について
　　　　　　行列 a[i][j] の要素を入力として受け取る
　　　　　　m[i][j] = a[i][j]
　　　　（繰り返し終了）
　　（繰り返し終了）
　　メッセージ文字列をユーザー入力として受け取る
　　i = 0 ～ 2 について
　　　　msg[i][0] = mes[i] - 65
　　（繰り返し終了）
終了

開始
関数 encrypt()
　　i = 0 ～ 2、j = 0、k = 0 ～ 2 について
　　　　en[i][j] = en[i][j] + a[i][k] × msg[k][j]
　　乗算結果の各要素に mod 26 を適用し、暗号文を出力する
終了

開始
関数 decrypt()
　　inversematrix() 関数を呼び出す
　　i = 0 ～ 2、j = 0、k = 0 ～ 2 について
　　　　de[i][j] = de[i][j] + b[i][k] × en[k][j]
　　乗算結果に mod 26 を適用して元のメッセージを取得する
終了

C++による実装例

#include<iostream>
#include<math.h>
using namespace std;
float en[3][1], de[3][1], a[3][3], b[3][3], msg[3][1], m[3][3];
void getKeyMatrix() { // ユーザーから鍵行列とメッセージを入力
   int i, j;
   char mes[3];
   cout<<"Enter 3x3 matrix for key (should have inverse):\n";
   for(i = 0; i < 3; i++)
   for(j = 0; j < 3; j++) {
      cin>>a[i][j];
      m[i][j] = a[i][j];
   }
   cout<<"\nEnter a string of 3 letter(use A through Z): ";
   cin>>mes;
   for(i = 0; i < 3; i++)
   msg[i][0] = mes[i] - 65;
}
void encrypt() { // メッセージを暗号化する
   int i, j, k;
   for(i = 0; i < 3; i++)
   for(j = 0; j < 1; j++)
   for(k = 0; k < 3; k++)
   en[i][j] = en[i][j] + a[i][k] * msg[k][j];
   cout<<"\nEncrypted string is: ";
   for(i = 0; i < 3; i++)
   cout<<(char)(fmod(en[i][0], 26) + 65); // 乗算結果の各要素にmod 26を適用
}
void inversematrix() { // 鍵行列の逆行列を求める
   int i, j, k;
   float p, q;
   for(i = 0; i < 3; i++)
   for(j = 0; j < 3; j++) {
      if(i == j)
         b[i][j]=1;
      else
         b[i][j]=0;
   }
   for(k = 0; k < 3; k++) {
      for(i = 0; i < 3; i++) {
         p = m[i][k];
         q = m[k][k];
         for(j = 0; j < 3; j++) {
            if(i != k) {
               m[i][j] = m[i][j]*q - p*m[k][j];
               b[i][j] = b[i][j]*q - p*b[k][j];
            }
         }
      }
   }
   for(i = 0; i < 3; i++)
   for(j = 0; j < 3; j++)
   b[i][j] = b[i][j] / m[i][i];
   cout<<"\n\nInverse Matrix is:\n";
   for(i = 0; i < 3; i++) {
      for(j = 0; j < 3; j++)
      cout<<b[i][j]<<" ";
      cout<<"\n";
   }
}
void decrypt() { // メッセージを復号する
   int i, j, k;
   inversematrix();
   for(i = 0; i < 3; i++)
   for(j = 0; j < 1; j++)
   for(k = 0; k < 3; k++)
   de[i][j] = de[i][j] + b[i][k] * en[k][j];
   cout<<"\nDecrypted string is: ";
   for(i = 0; i < 3; i++)
   cout<<(char)(fmod(de[i][0], 26) + 65); // mod 26を適用して元のメッセージを取得
   cout<<"\n";
}
int main() {
   getKeyMatrix();
   encrypt();
   decrypt();
}

実行結果

Enter 3x3 matrix for key (should have inverse):
1
0
1
2
4
0
3
5
6

Enter a string of 3 letter(use A through Z): ABC

Encrypted string is: CER

Inverse Matrix is:
1.09091 0.227273 -0.181818
-0.545455 0.136364 0.0909091
-0.0909091 -0.227273 0.181818

Decrypted string is: ABC