update: 9/05/2008

暗号理論の応用を試みた行列変換のあれこれ。そのレポートです。


Top Page へ
Contents
 

◎　暗号化と変換 

◎　ASCII 表の変換
◎　行列変換の利用

◎　行列次元と非正則の関係 

◎　逆行列変換の問題と実際

◎　プログラム改良で起きる問題

◎　文献

 


◎ 　暗号化と変換
 
現在の暗号化技術の主流は素数を暗号化鍵として用いる方法ですが、
数学的な変換には逆行列のように特別な鍵を用いないで行える変換もあります。
厳密には鍵の要素が少ないという意味ですが。
 
暗号化方法
暗号鍵
変換
手続き
キーワード、暗号表、素数を使う
決められた操作で変換する
特徴
暗号鍵が不明な場合、解読が困難。
暗号鍵の安全記憶が必要。
変換操作が解読されやすい。
平文の情報だけで変換可能。
可逆性
ほぼ可能
不可能な場合も多い
代表例
ナンバー錠、パスワード、公開鍵暗号方式
シーザー暗号、行列変換
 
 
 
　
top 
 


◎ ASCII 表の変換
 
コンピューター上で、暗号化を多段階に行うには数値に置き換えての
操作が必要ですが、英数文字は次のような ASCII コードに置き換えられます。
 
文字
１６進数
１０進数
０〜９
0x30 - 0x39
48 - 57
Ａ〜Ｚ
0x41 - 0x5A
65 - 90
a〜z
0x61 - 0x7A
97 -122
 
 

top 

 

◎ 行列変換の利用
 
ASCIIコードが整数であるので、何らかの変換後の数値も整数範囲であれば、
記憶容量、復号化の点で有利といえます。特定の鍵となる情報が必要のない
変換と言えば、逆行列変換が適度な暗号化レベルの方式な気がしますが、
正則で無い可能性、変換後に小数が出現することもあり、記憶容量が
無駄になるだけでなく、適当な少数点桁での打切りによる復号時の
計算ミスの可能性が出るかもしれません。
 
もし適当な小数点桁でデータ保存しても、ASCIIコード整数値に再変換
できるなら、非正則の場合（ 行列式 det = 0 ）のみ別の変換をすれば
暗号鍵への依存の少ない変換が完成しそうです。
 
試案として、行列変換の主流である回転変換を行う方法があります。
メッシュ方式にすれば、変換後に整数として記憶できるので、
復号時も整数からの変換となり出現する整数近傍の
値を四捨五入ぐらいで元の整数化ができそうだからです。
 

 
 
行列変換主体の暗号化フローチャート（案）
 

 
top 
 

 

◎ 　行列次元と非正則の関係
 
非正則（ det = 0 ) の場合は、行列の次数と要素の範囲により、
変化しますが、実際に何％ぐらいの割合で非正則の場合が
現れるのか計算しました。 ２ｘ２行列で det = ad - bc とすると、
例えば、 積が６の場合　1x6, 2x3, 3x2, 6x1 に対して、
積が 7 の場合、1x7, 7x1 の組合せしかないなど、要素範囲に
比例的に増加するわけではなく、素数の影響が伺えます。
次表は、要素範囲を１〜ｎの整数とした場合の計算結果です。
 
  2x2

要素の上限値 n 
1
2
3
4
5
6
7
8
9
10
15
20
50
100
det=0 の個数
1
6
15
32
49
86
111
160
209
278
703
1360
10950
52160
非正則の割合(%)
100
37.5
18.5
12.5
7.84
6.64
4.62
3.91
3.19
2.78
1.39
0.85
0.175
0.052

detの総組合せ数 = n4
 
3x3, 4x4 行列にもチャレンジしました。Ｃ言語のプログラムは Pentium 
200 [MHz] で回しました。3x3 行列の計測区間では n に応じて 4 倍ぐらい
処理時間が増加していきます。（後図のように比率は n とともに低下 )
n = 7 で１分３０秒ならば、n= 8 では６分ぐらい。(実際は５分２０秒）
閑な人間とはいえ、５分ぐらいが待ち時間の限界です。
さて、最新機種のカタログでは１０万円ぐらいの　2 [GHz] Dual core の
廉価製品があります。もしこれをを導入したならば、処理速度が１０倍になり、
n = 7 の時、計算時間は９秒に改善されますが、n = 10 ではもう１０分弱に
なります。これはＰ問題（入力Ｎの大きさに対して２乗、３乗で表される
時間以内に計算できる問題）に関する事例だと感動しました。この場合、
追加的な３つのデータを得ると、もう旧型マシンの限界に当たります。
 
  3x3

要素の上限値 n 
1
2
3
4
5
6
7
8
　
det=0 の個数
1
248
3975
29104
119405
436818
1105537
2790818
　

非正則の割合(%)
100
48.4
20.2
11.1
6.11
4.33
2.74
2.08
　
計算時間[s]
 
　
　
　
　
5
25
97
5m20s
　

detの総組合せ数 = n9
 
  4x4

要素の上限値 n 
1
2
3
　
det=0 の個数
1
33472
7382001
　
非正則の割合(%)
100
51.1
17.1
　
計算時間[s]
　
1
6m56s
　

detの総組合せ数 = n16
 
 

 
 
話を戻すと、今回のプログラムでは、ASCII コードの48〜122 が
範囲であり、平文を正方行列にした場合に行列次元は３〜１０程度なので、
非正則の割合は１％未満と推定して良いでしょう。これぐらいなら非正則の
場合は省略しても良さそうです。
 
計算プログラム（Ｃ言語）
 
掃きだし法による確認と例外
 
top 
 


◎ 　逆行列変換の問題と実際
 
逆行列が存在した場合の話を進めます。逆行列変換の結果、
小数値が出現することがあります。ある要素が循環小数で 0.33333... 
double 型では、E(-308) - E(308)の範囲で対応可能です。
実際のデータファイルでの保存は、なるべく少ない小数点桁で保存して
問題なく再変換できる必要があります。例えば、0.33 で保存した場合
0.00333... はロード時に再現されません。小数点桁の保存の差異が
再変換の時にもし、0.83/0.33 = 2.52、 0.83/0.333 = 2.49　のような
プロセスを経ると、四捨五入時に異なる整数値になります。
 

 
実際は式のように、n=100 の場合、切捨てた小数εは小数点２桁以降なら
(1-0.09)/(1+0.09f)のように整数値へ四捨五入が可能ですが、f は最大でも
100 の位ですので、小数点４桁以降の切捨てなら再変換が問題なくできそうです。
 

 
3x3 については、掃きだし法で丁寧に計算を続けていくと、
要素(2,2) では分子の方は、小数点２桁に抑えるために
εは小数点４桁になります。これに対して分母の方は、
最大で 105 弱の可能性もあるので、εは小数点７桁なら安全です。
しかし符号を見ると係数 f が打ち消しあいそうなので、
分子に合わせて小数点４桁ぐらいでもよさそうです。
他の要素も対称性から同じオーダーになるでしょう。
 
top 
 


◎ 　プログラム改良で起きる問題
 
      次のページを見る...
 
 
top 
 


◎ 　文献
 
・ 暗号の数理　作り方と解読の原理  一松 信著　講談社

 
top 
 


 
  調査レポート作成 :tmlbworks