１．素数を使ったメッセージの埋め込み
暗号文を31987=>15bitとする。
この数の中に3つのメッセージが入っている。
つまり、8191を法として次のような数列を考える。
$p$を一つの素数とし、$m_n$で$n$個のメッセージで表すと、
$c=m_1+m_2p+m_2p^2+...+m_{n-1}p^{n-1}+m_np^n$
と書くことができる。
ここで例を挙げる。
ベクトルの基底となる数に$p=17$を選ぶと、3つのメッセージ$m_1=10,m_2=11,m_3=110$を次のように折りたたむことができる。
$c=10+11* 17+110* 17* 17=31987$
メッセージの2進長さは4+4+7=15ビット。
暗号文のサイズは31987％8191＝7414＝13ビット
ここで秘密鍵は8191と3と17であるとする。
つまり13ビットの暗号文空間に対して、秘密鍵を使うと常に15ビットの通信チャンネルが存在し、任意の文章を組み込むことができる。
このような数の組み合わせを最適化することで、暗号文のサイズに大して最大の情報量を持つように調整することができると思われる。
2.復号方法
逐次復号
メッセージを1つずつ復元する。
$m_1=c \pmod p$
$c-m_1 \mod {p^2}=m' \pmod {p^2}=m_2p$
$m_2=m'/p$
.
.
.
以下同様。
このほか最大公約数を求める方法で代数的復号により$m_i$を効率的に計算できると思われる。
復号法は1つずつ17で剰余をとって計算することもできるが、ここはユークリッドアルゴリズムを使って復号するのが効率的である。
つまり、この暗号文の代数的な構造を使って復号することができる。
安全性
このようなチャンネルは秘密鍵を知らないと見つけることができない。
これはよく新聞の記事を縦に読むと普通の文章が現れるが、横に読むと別のメッセージが現れるというトリックの暗号バージョンであると考えられる。
この通信は盗聴者が暗号化の結果を知らないという前提の下で安全であると思われる。
今後の課題
この方法を最適化して、最大の通信容量を達成する秘密鍵とパラメータの構成法を見つけるのが今後の課題である。
鍵の生成には整数計画法や線形計画法を使うことができると思われる。
更にこの方法は整数だけでなく多項式の係数ベクトルに大しても同じような通信路を獲得することができるであろう。
まとめ
素数を使ってデータの中にメッセージを埋め込む方法を考え、その復号方法を与えた。