乱数と暗号の部屋　（暗号工房）

高速公開鍵暗号，量子コンピュータに対抗できる新型公開鍵暗号，超長周 期擬似乱数，ファ イル暗号化ソフト

新方式の公開鍵暗号を開発しました。Elgama暗号タイプの公開鍵暗号(Diffie-Hellman鍵共 有)で，デジタル署名にも対応しています。
nを100程度の自然数として，素数を法とする剰余体K上のn次方程式
     xⁿ－σ₁x^n－1＋σ₂x^{n －2}－σ₃x^n－3＋…＋ (－1)^n－1σ_n－1x＋(－1)ⁿσ_n＝0
を考えます。
この方程式による体Kの拡大体での， この方程式の解をα₁，α₂，…，α_n　とするとき，α₁^p，α₂^p，…， α_n^pを 解とするxⁿの係数が1のn次方程式を考えると，対称式は基本対 称式で表されることにより，Elgamal暗号(Diffie-Hellman鍵共有)タイプの公開鍵暗号が構成できます。
さらに，デジタル署名 も構成でき ，署名長は公開鍵長の2倍です。
通常のElgamal暗号は有限体の離散対数問題を暗号の強度の根拠としていますが，この暗号を解くには，有限体上の多次多変 数方程式を解く必要があると思われます。この暗号こそ，量 子コンピュータが実現し てRSA暗号，Elgamal暗号，楕円曲線暗号が滅びたときにも生き残る，「世界最強の公開鍵暗号」です。

Chebyshev多項式によるElGamal暗号型の公開鍵暗号を，方程式による拡大体の観点から見直し，合成数を法とする と，Rabin暗号と同じく，安全性の根拠を大 きな合成数の素因数分解の困難さとすることができることを示しま した。
基本周期が最大となる公開鍵において，「Ｎ＝pqの素因数分解できない⇒離散対数問題の解は求まらない」こ とが証明できる暗号で，暗号化・復 号時間は共に通常のElGamal暗号の4/3倍かかります。
しかし，有限体上のElGamal暗号に対する高速解読法が一切使えないため，冪乗の指数を小さくすることができ，2048bitの暗号で冪乗の指数を 112bit程度に小さくとれるものと思われます。
また，このとき，デジタ ル署名では，RSA署名と比べて署名生成が3.4倍高速となり，署名長はRSA署名と同じです。
また，中国人剰余定理を用いて，ElGamal暗号やRSA暗号の復号を桁違いに高速化する方法を開発しました。こ の方法は，RSA暗号では暗号化の高速性がなくなりますが，ElGamal暗号には影響しません。
暗号化と復号を総合すると，この暗号が「世界最速の公開鍵暗号」であり，安全性と速度で「RSA 暗号を超える公開鍵暗号」です。

RSA暗号は，暗号化は極端に高速であるが復号が遅い。これを逆にして，暗号化は遅くなるが復号を極端に高速とする方法を 考えま した。ポイントは，中国人剰余定理を活用することにより，復号のときの冪乗の指数を2つに分けて，指数を極々小さくしても安全を保てる ようにしたことです。ただし，暗号化のときの冪乗の指数は大きくなるため，暗号化は遅く なります。また，この方法により，RSA署名の署名生成と検証の計算コストも逆転します。この方法は，SSL/TLS通信におけるサー バー側の負荷を軽減し，ICカードの認証でも，ICカード側の負荷を軽減すると思われます。さらに，通常 のRSA暗号と，このRSA暗号を組み合わせれば，CPUパワーの弱い側の負荷をほとんど無くすことができます。(2015年5月)

ElGamal 暗号に中国人剰余定理を用いて復号処理を高速化する方法を考えました。さらに，暗号化の冪乗の指数を小さくしても安全であると考えられる方法を考えまし た。これによりElGamal暗号が「世界最速の公開鍵暗号」となります。ただし，公開鍵が通常のElGamal暗号より大きくなりま す。第一のポイントは，p，qを素数として，合成数N=pqを法とする剰余類上に暗号を構築したことです。これにより中国人剰余定理 を用いて，復号の冪乗の指数を小さくすることができます。第二のポイントは公開鍵の数を増やして，暗号化の冪乗の指数を小さくしても低指数攻撃を避けられ るようにしたことです。また，通常のElGamal暗号は離散対数問題の困難性を安全性の根拠としますが，このElGamal暗号は合成数N= pqの素因数分解の困難性を安全性の根拠とします。
以下に， 通常のElGamal暗号の復号の冪乗の計算量を1として，冪乗の計算量の見積もりを示します。

冪乗の計算量の見積もり

暗号強度

法のbit数

RSA暗号

変形RSA暗号

Chebyshev暗号

ElGamal暗号

高速ElGamal暗号

RSA署名

変形RSA署名

Chebyshev署名

暗号化

復号

暗号化

復号

暗号化

復号

暗号化

復号

暗号化

復号

生成

検証

生成

検証

生成

検証

112bit

2048bit

僅少

0.25

1

僅少

0.15

僅少

2

1

0.11

僅少

0.25

僅少

僅少

1

0.073

0.15

128bit

3072bit

僅少

0.84

3.4

僅少

0.38

僅少

6.8

3.4

0.28

僅少

0.84

僅少

僅少

3.4

0.19

0.38

192bit

7680bit

僅少

13.2

53

僅少

3.5

僅少

105

53

2.6

僅少

13.2

僅少

僅少

53

1.8

3.5

ただし，RSA暗号や署名では，法とする数より小さい数を掛けるため，計算量は上記より減少する。
また，積の計算量は法のbit数の2乗で見積もってい るが，Karatsuba法を用いれば計算量は減少する。その場合でも，同じ暗号強度で比べれば，各暗号の計算量の比は変わらない。

フィボナッチ数列のような隣接多項定数係数線形漸化式を高速に計算する方法であり，特に有限体上の漸化式において有効である。こ のアルゴリズムは，特に有限体上の漸化式において有効であり，隣接n項定数係数線形漸化式で第N項を求める場合，全体の計算量はn²log₂N のオーダーである。高 次対称式暗号においても， この考え方を使っている。また，行列の整数乗も，ケーリー・ハミルトンの定理（固有方程式）を用いれば，この方法で高速に計算できます。

著書「16歳のセアラが挑んだ世界最強の暗号」で有名な「セアラの暗号」は，非可換行列と，行列の累乗を用いたものですが，脆弱 性がありました。
また，「解読不能は数学的に証明済み」と主張した「CAB方式の暗号」も，公開鍵暗号部分に，非可換行列と，行列の累乗を用いてい ます。 
その主張には重大な誤謬があり，CAB方式の暗号は，有限体上のElgamal暗号と同等であり，同じ暗号強度で比較すると，有限体上のElgamal暗 号に対して鍵長や計 算速度で圧倒的に不利であると数学的に証明できます。

M系列の乱数（最長線形帰還シフトレジスタ）を32ビットずつ出力するプログラムです。単純なM系列乱数でも周期が長ければ，ま た，原始多項式の項の数が多ければ，Mersenne Twister のような高品質な乱数になり，Mersenne Twister のような複雑な理論が必要ないのではないかという疑問から作りました。独自のプログラムで見つけたGF(2)上 の原始多項式を用いたもので，周期はメルセンヌ素数 2²³²⁰⁹-1 で ，全周期では725次元超立方体に均等分布します。漸化式の項の数を多くすることにより，ビットのかき混ぜを十分に行うと共に，Tempering 部分を非線形にして，良質の乱数を出力するようにしました。また，Mersenne Twister と同周期，同ワーキングメモリのものも作りました。さらに， 周期がメルセンヌ素数 2²¹⁶⁰⁹¹-1≒10⁶⁵⁰⁵⁰ で，5項間漸化式のものを作成しました。全周期では6752次元超立方体に均等分布します。世界最長周期レベルの乱数です。これらの乱数には， 0≦x＜1の実数の一様乱数の高速なコードを組み込んでいます。
また，ストリーム暗号用に改造 したコードも作りました。シンプルな改造ですので，使用メモリは大きくなりましたが，生成速度はもとより若干遅くなった 程度です。

固定小数点数のC言語による関数ライブラリを作成しました。math.h の関数の大部分をサポートし，世 界最高レベルの速度を実現しました。
また，ライブラリでも使用した，高次収束のニュートン法を解説しまし た。

三角関数を高速に計算する方法を考えました。2倍角の公式を用いて角 を小さくしループの回数を減らし，除算の部分をコンパイラに乗算に変えさせて除算を一度も用いていないことによります。c言語のdouble型で 効果があります。問1は，

長周期で高速な擬似乱数で，ファイル暗号化ソフト「暗GO」の暗号化ルーチンに使っています。ストリーム暗号にはも ちろん，大規模シミュレーションにも使えます。
NIST Special Publication 800-22の乱数テストで確認しました。

「暗GO」は強力な暗号化アルゴリズムを用い，個人が日常的に使う時の操作性を第一に設計した，Windows用の ファイル暗号化ソフトです。
ファイルやフォルダ（複数選択可）を「暗GO」のアイコンや，起動した「暗GO」上にドラッグ＆ドロップして，暗号化，復号化すること ができます。
圧縮・解凍機能があり，暗号付き圧縮ソフトとしても使えます。
実行ファイルを作成でき，「暗GO」がなくても復号することができます。
暗号化は，256bitブロック暗号と，「無限階層法」によるストリーム暗号のハイブリット方式で，パスワードは半角64文字（512bit）まで入力で きます。

「公開鍵暗GO」は，「暗GO」の姉妹作品の公開鍵暗号化ソフトで，使いやすさを第一に設計しました。公開鍵暗号と 秘密鍵暗号のハイブリッとによる暗号化を行っており，非常に高速に暗号化，復号化ができます。公開鍵暗号の部分は「世界最速 のElgamal暗号」を目指して作りました。
暗号化の原理と，ソフトの主要部分のコードを掲載していますので，詳しくお知りになりたい方は，そちらをご覧下さい。また，SHA-256，SHA- 512のコードと，SHA-256を用いたデジタル署名のコードを掲載しました。

「(仮称)十進BASIC」上で，試行除算とミラー・ラビン素数判定法を用いて素数か合成数かを判定するプログラムを作成しまし た。また，この素数判定プログラムに，ポラードのρ素因数分解法を 加えて，素因数分解が出来るようにしました。

π/4を求める逆正接公式(Machin-like formula)で，6項では最良の次の公式を 導きました。
    π/4=83arctan(1/107)+17arctan(1/1710)-44arctan(1/225443)-68arctan(1/2513489)+22arctan(1/42483057)+34arctan(1/7939642926390344818)
また，π/4を求める新方式の逆正接公式探索法を考え，7項では最良の次の公式 を導きました。
    π/4=22arctan(1/28)+arctan(1/275807)+2{arctan(1/142057)-arctan(1/99368343)-arctan(1/54838715017299308)-arctan(1/88942800178226109582168404411725)+arctan(1/61775097240445660329693394511093237957733203657982660526882)}

Quick SortとMerge Sortでどちらが速いか？
Merge Sortを改良して，Quick Sort以上に速くしました。Merge Sortはマジに速いソートと言ってよいでしょう。
N分木ヒープソートをコード化したところ，データ数が少ないときはクイックソートより速い速度が得られました。
クイックソート（quicksort）とN分木ヒープソートを組み合わせて，超高速安全クイックソートを作りました。
また，3D median fiiter 用としては世界最速な中央値を求める関数を作りました。
クイックソートとクイックセレクトを組み合わせて，Quicksort killer sequenceを実際に作ることが不可能な ソートのコードを考えました。

多倍長整数演算，モンゴメリ乗算，BSA法（Binary Splitting Algorithm）の解説と，ニュートン法と類似の方法で計算量がO(n(logn)³) となるはずの円周率の計算法を掲載しています。円周率を4通りの方法で10億桁求めました。

数値積分におけるシンプソンの公式やブールの公式を，台形公式の様に変形した，平均すると台形公式より収束が速いアルゴリズムを 考えました。さらに，和を求めるのに，順番に足していくのではなく，二分木構造により和を求めれば，数値積分における丸め誤差の集積が起こらないことを発 見しました。

m系列乱数を元に作成したもので，周期が2¹²⁷⁹-1以上である ことが期待されます。ストリーム暗号に使うことを想定して作ったものですが，大規模シミュレーションのにも使えます。乱数性はNIST Special Publication 800-22rev1 の乱数テストで確認しました。

数学好きな高校生にも役立ちそうな、数学関連の解説を掲載しています。

2017年の大阪大学の物理の問題について，数式を用いた解説を書いてみました。また，同じ問題の問1も出題ミスと断言できます。