cf. PKP-Based Signature Scheme : Beullens, Faugere, Koussa, Macario-Rat, Patarin, Perret
秘密鍵暗号、削除済み。
久しぶりに乱数。 iso.cがそれ。 色々いじって、以前完成したと思っていた置換乱数をstsの改良バージョンとかいうやつに読み込ませたら、全然だめだったので色々いじっていた。 Random Excursions Variantが全滅だったのだ。
今日思いついた計算式を追加したら、まるで生まれ変わったかのような性能を発揮した。 実際生まれ変わったんだろうけど。 同じ数列を2つに分けて、片方にはs-box（変換表）、もう片方には普通に置換した数列。 この派生した2つの数列を足し合わせるというようなことをやったらうまく行ったのだ。 良くない乱数のときは置換とベクトルの半直積として記述できたのだが、（1つの数列を2つの要素で記述できる）今回のはその代数的記述が思うように行ってない。 多分記述できるんだろうけど、その方法がわからないというか。 どんなアイデアでも説明できないんじゃだめだ。 最初のがだめなだけだったのかもしれないが。（何故良い結果が出ていたのだろう）
よくわからないから安全などということは良くない見本ではあっても、いい見本ではありえない。 それで改良型STSの方でも毎回ほぼ満点が取れる乱数になった。 正確には今まで統計テストを実行して1回もだめな判定なかったというレベルの乱数。 最低でも100回は実行している。 それでも101回目に落ちるかもしれないというのは統計の恐ろしさ。
この程度の検査に合格しない乱数なんて話にならないと言われたので多分これで平均になったのだと思う。 CSPRNGへの道のりは遠い。
秘密鍵暗号をやっている。
分かったようなわからないような。 多分わかってない。 説明できないから。 何でコーシー行列を使うといいのか？ SPN構造にはどんなおまじないがかかっているのか？
うーん数秘術だｗ
やっぱり速度とかメモリとか制限がある時には設計が難しくなるのだと思う。 攻撃法を理解しなければならないのと、１６ビットマイコンで動く１２８ビットブロック軽量暗号を目指す！ｗ
流石に８ビットで動かすのは無理があるけど、ポケコンを使って暗号化したい。 アスコンは６４ビットだから動かない。
ポケコンで符号ベース暗号を動かすのは絶望的に遅いと思う。 秘密鍵のプログラム自体は２００行行かない位なので、公開鍵よりめっぽう少ない。
実装のためのコストを減らすことで、理論も目を通しやすくなっているのかもしれない。
今迄SPNをやってきたが別の方式もやってみたい。 例えばツーフィッシュとかサーペントとか。 安全性解析はちょっと面倒だけど、差分解読と可なら参考資料があるし本にも詳しく乗っている。 DESは線形解読法で完全に破られたし、余りその事実は広まってないみたいだけど。 一週間くらいかかるけど解読法をやってみたい。 フルに時間が取れればできるけどできない時を考慮すると２週間くらい見ればいいかも。 興味が持続すかどうかも重要だ。
それが終わったら目標はカリーハワード対応。 これならどこもやってないだろうし、やる意味はあると思う。 秘密鍵暗号の論理。
とりあえず完成。ファイル名はwow.c。
これから攻撃法を考えます。
鍵ストリームをオリジナルに工夫した。
これは以前実験した経験に基づいている。
共役置換を使って鍵データと自分自身の排他的論理和を取ると、質のいい乱数が高速に計算できるというものだ。
置換は鍵をシードに計算される。
つまり鍵がなければ写像が決まらない。
これは相手も鍵を共有していれば問題ないが、置換に不動点がないように取らなければならない。
もう一つはs-boxだ。
これは非線形関数を実現するために$x^7 \oplus c$となるように事前計算したテーブルによって実現している。
この変換は線形でないだけでなく、アフィン変換でもない。
どの点でそうなのかはわからないが、AESは代数的な構造が単純すぎるとの批判もある。
例えば、DESは群でないことが知られていたが、AESにも同様な性質があるかどうかは知らない。
暗号化の本体はビジュネル暗号だ。 もう一つ欲を言えば、エニグマのような確率性を導入したいが、これは今後の課題である。 今の仕様では、鍵が固定のとき暗号化は確定的である。 置換の生成がラウンドごとに再計算されるため、一見すると同じ文字でも異なる文字に変換されているように見える。 内部的に見れば、鍵のバイト列の位置が置換により変わっているだけであり確率的であるのとは違う。 あと今のままでは鍵が０だと置換された平文がそのまま出てくるので、ナンスとして０でないベクトルを拡大鍵のシードに選ぶ必要がある。 今回の実装ではnonceの値を固定した。 このような固定したナンスでも、2つの置換が秘密であればラウンド毎の拡張鍵を特定するのは難しいのではないかという予想である。
設計にあたってはDESを参照にしたつもりだけど、あてずっぽうな部分もあるので、既存の解読法を参考に攻撃法を考える予定である。 この暗号には排他的論理和が使われていない。 他の暗号で排他的論理和が使われているのは、何かセキュリティ上の目的があるのかもしれないが、よく知らない。
DESがデータを半分に分け、片方にカギを足してS-boxで変換をし、もう片方にXORし、交互にこの操作を繰り返すという手順をとっている。 この計算手順自体は何か数学的な目的があったのかもしれないが、今のところ詳しくは知らない。
wowは置換を生成し、ビジュネル暗号化し（拡張鍵を平文ベクトルに+する）、S-boxで非線形変換をする。（ただし置換は秘密鍵に依存する）、 更に行列型に配列を変形し、行列の各行を１バイトずつ巡回シフトし、ヴァンでルモンド行列をかけて平文を撹拌し、 最後に暗号文を置換するという事をやっているが、数学的に盲目な設計のためにすぐ解読できるだろうことを期待している。 このように秘密鍵に依存するパラメータが多いほど秘密鍵は大きくなるので安全なのかもしれないが。 AESもどきのような暗号ができたが、なぜそうするのがいいのかを説明することができない。
本当は順番まで意識しないといけないのだが、理解してないので何故だめなのか説明できない。 例えばAESやDESは平文が自分自身と干渉して鍵とうまく混ぜられているが、wowでは平分が自分自身とは混ざっておらず、 容易に鍵を特定できてしまう。 で、考えてみたのだが解ったのはmixcolmnは平文同士を混ぜるためにあるのだと。 その前のshiftrowは行列の計算が縦ベクトルだけで計算されると混ぜるときになにか影響が出るのでずらしているのではと。 自前の関数にも期待すべき効果があるはずだが、大本のAESがどのような理論で構成されたのかを理解するまではおそらくわからないままだろう。
開発目的は攻撃法の理解のためである。 解読できるかな。
このAESもどきはブラインド署名とは無関係に出てきたものなので、分離して再公開する可能性があります。
秘密鍵暗号をやっている。 公開鍵暗号の方がやる価値があると思っていたけど、コードの量でいえばはるかに作りやすいし、攻撃と設計の関係を勉強するにはちょうどいいのかも。 秘密鍵暗号のことはほとんど知らなかった。
今迄の私の考えは間違えていた！ ちゃんと１行ずつどのような処理が必要なのかを説明できるようなコードにしないと読めないだけでなく無駄なコードをなくせないのだという事に気が付いた。
で、有限体を作るプログラムをいじってたんですが、今まで教科書にあった正規基底だけしか計算してなかったので、 普通の既約多項式から作る多項式基底は全く計算できなかった。 でも、既約多項式があれば逆元計算ができるし、これは何かおかしいと思って作りなおしたのだ。 原始元が２以外になるだけで他は何も変わらないのだと思うけど、今回はそういう作り方をしてない。 ある値とその逆元を配列に入れただけだ。 ちょっと時間がかかるけど、自分のコードが動くようになった。
書いたコードが正しく動くかどうか自動的に検証する方法があるらしく、その方法について調べている。 日本語ではただ１冊。 最初７千円だったのが翌日には１４０００円を超え、ついには１冊もなくなった。 へへーん、そんな手にのらないもんねー。
私は図書館で借りて必要なだけコピーします！ 書籍なら半分までコピーできます！
公開鍵で新型はできなかったけど、秘密鍵暗号ならできるかもと甘い考えをしている。 論理学やらねば。
ちょっとわき道にそれますが、ブロック暗号の安全性がどのように議論されているのかに関心を持ちました。 AESのラウンドごとの処理を、ビジュネル暗号を使って分析してみようかと思います。
あと、ちょっぴり軽量暗号なんかにも興味を持ったり。 例えば、パスワードからリアルタイムのハッシュ値を計算するのに軽量暗号を使ったりとか、その場合にSHA3とどちらが早いかとか。
限定公開の記事はこちら！！
https://qiita.com/tznamayo/private/dd3b2ba77df77fde5fb0
鍵（平文？）をS-Boxでランダムに見えるようにすることに効果があるという意見はここに見つけましたが、理由は何故だかわかりません。 置換で変換パターンをランダム配置にすると難しくなるという私のイメージと同じものなのかどうなのか？ https://ja.wikipedia.org/wiki/%E3%83%B4%E3%82%A3%E3%82%B8%E3%83%A5%E3%83%8D%E3%83%AB%E6%9A%97%E5%8F%B7
これはむしろ短い固定長の鍵を使う事で、特に暗号化のブロック長以下の長さの鍵が使われると鍵の周期がパターンとして表れやすくなるので、 同じ文字が暗号化されていればその部分を抜き出して、更に頻度解析を行うことができるという事だろうか？
これがAESのブロック長より長いサイズの鍵を使った場合にどう説明できるか、が大事になると思う。 でもこれも短い鍵を使うと多標識暗号は攻撃にかかりやすい、という原理さえ把握しておけば、 例えば２つの置換を再帰的に使う事でブロックをまたぐような長い周期のラウンド鍵を生成することが安全性を高めることになるともいえる。 そうすると今回の私の実装も（細かいことは何も説明してませんが）ある意味ビジュネル暗号の改良に成功しているかもしれない。
で、現代の暗号であるAESは菓子スキー検査にはどのくらい強いのか？
そして現代的なブロック暗号に対する攻撃法である線形解読法や差分解読法に対してビジュネル暗号とその改良バージョンはどのくらい強いのか？ これに対抗できないと話にならないのですが！ｗ
それぞれがどのような意味を持つのか楽しみですが、今日は調べたりコードを書いたりするので疲れてしまったのでおしまい！ｗ
ベクトル置換（あてにならない思い付き）:置換の代わりにベクトルをやり取りする
１．公開鍵の生成
1-1.置換群
1-2.自己同型群の位数Mが32以上であることを確認する。
1-3.そうでなければ1に戻る。
1-4.ベクトルに置換を繰り返しかけて（どうかけるかにもよる）、M回のラウンドごとに差分の和
ここで何が問題になっているかというと、置換
今のところ、この条件を満たす
２．認証
2-1.32バイトの乱数ベクトルを生成し、それをRとする。
2-2.Rに置換をかけ、その差分の和
2-3.検証者は０か１を証明者に送る。
2-4.検証者のチャレンジが０の時、
証明者はRを送る。
検証者のチャレンジが１の場合、証明者は
検証者は
論文と教科書の間を行き来するうちに、なぜPKPがうまくいくのかについて気づいたこと。
まだ完全に理解してないけど、例えばベクトルと鍵となる置換の関係であるとか、
それが核と像の対応をどのように使っているかとか、とてもよくできているという事に気が付く。
ではなぜ自分の方法ではだめなのかについても、そのうち分かると思うアハハ。
例えばベクトルが全部同じ値だと同じになるので、置換と数列を1対1に対応付けるパラメータとしてベクトルが機能してない。
なので、このままではだめである。
例えば、ベクトルXの値の違いに関して数列が影響を受けるような計算をすればこの問題は解消する。
ああそうか、あったわ。 例えばベクトルに置換を掛けたものを、元のベクトルに足すという方法で異なる数列を生成することができるはずである。 そしてそのベクトルにラウンドごとに繰り返し置換を書けて足したベクトルの連接にハッシュ関数にすれば、 そのハッシュ値の列はベクトルが固有なので全部同じ値でもほかのベクトルと一致しなくて済む。
線形写像の整数バージョンは確かまだないはずだ。 うだうだ考えても無駄なので今度これを数式化する！
ベクトルの値を足して好きな数で剰余をとるなどの方法もあるが、この場合は2つの異なるベクトルの合成として数列がうまく記述できなければならない。
・・・で、今ここで数列に相当する値としてシンドロームを計算することを考える。
エラーベクトルに置換をかけたやり、重みを変えないようにエラーベクトルを変形する。
ここで数列の代わりにシンドロームを使えば、ベクトルの重みを変えないという条件付きで置換とシンドロームが1対1対応であるという条件を満たす。（これは大した制限ではない気がする。）
更に2つのエラーベクトルの排他的論理和とシンドロームの排他的論理和が対応するという条件も満たす。（線形写像っていうくらいなので）
これなら置換の代わりにベクトルを使うという方法にマッチする。 ああもうスターン署名とかであったのかｗ。 この視点で考えられているのかもしれないけどそうでないなら何かあるかも。
まさかPKPが符号になって生まれ変わるとは。
なんで置換を使っているのかわからなかったけどそういう事ね。
確か符号ベースのブラインド署名もあった気がするけど、何これ何で置換するのわかんねって感じで放棄してたのが今復活の予感。
要するに、ベクトルの重みを変えない計算なら何でもいいという事。
q-ary符号というのはワイルド符号のことも含むのだろうか？
ちゃんと読んでないからよく知らないけど今度読もう。
もっとうまくできないか考えてみます。 例えば線形写像を定義するのに、必ずしも符号でなくても1対1写像を定義できれば新しいかもしれない。 これはかなり適当な思い付きなので検証が必要ではある。 例えばｎ次元ベクトルに対して、ｎ変数多項式を使うなど。(Hashing with polynomial) これらは線形写像の一般化である。
更に材料を変えることを考えると、ベクトルの要素として2次元の整数の対を使って、半直積（アフィン変換）に置換群を掛けたり、 平面上の点のベクトルを２変数多項式への代入値として数列$\alpha$を計算することができる。
これらもまた考察に値するものと思われる。 線形写像と計算に使う材料の一般化を考えてみたいと思う。
何だか頭のよさそうな外人を見かけるので、日本で国際学会が開催されているのかもしれない気のせいかも。（もしかして近くで起きてる？）
このエラーベクトルバージョンもとい、一般線形写像バージョンは今後記述するだろう。
何だかジャックアタリの本で遊んでる場合じゃなくなったなｗ
PKP-DSSの署名サイズは70キロバイト超えるよという話。
PKP-IDSからPKP-DSSの流れ。
実装はこの通りじゃありません。独自解釈が入っています。オリジナルはもう少し後で書きます。
秘密鍵をsk、公開鍵をpkとする。この時、
整数ベクトルの隣接する要素の差の総和をとることでハッシュの代わりとしている。
２つの置換$$P,Pa$$を$$P_k=P^{k}[i]$$とし、$$P_k$$をベクトル$v$にかけて$$v[i]^=v[P_k[i]]$$とし、$v$をラウンドごとに更新し、
このベクトル$v$の要素の差分の総和$$\sigma(v[P[i]^v[P[(i+1)%N])$$を署名ベクトルとする。
ここでベクトルは小さな素数pを、例えば$p=4093$位にとり、置換の次元を$N=106$位にとる。
rはランダムベクトルとする。
return c0,c1
検証：
2.
c <- F_p
return z
if b <- 0
if b <- 1
if b=0
if b=c
PKP-IDSの流れは、こんな感じである。
署名作成：
\phi(1..289)：ランダム置換
r(1..289)：ランダムベクトル
c1,c2,...,c289 <- H(m||com)：ハッシュ関数からｃを作成
rsp1=z(1..289)
b1,b2,..,b289 <- H(m||com||z)：ハッシュ関数からチャレンジビットを生成
return (com,rsp1,rsp2)
署名検証：（m,(com,rsp1,rsp2)）
c(i) <- H(m||com)
b(i) <- H(m||com||rsp1)
rsp1 -> z(i)
... orz（理解不足）
PKP-DSSのサイズを小さくできないかと思って作った爆笑署名。この問題の背景には、置換群の持つ軌道が、その置換に対して固有であり１対１対応になるだろうという予測に基づいている。
多分これから証明する上で欠陥が分かってくると思う。というか証明なんか理解できないかもしれないのに。
で、例えば次元$$N$$の巡回置換を例にとろう。Pが位数ｎの置換であるとき、その置換の軌道をラウンドごとの置換の連接にハッシュをとったものに対応付ければいい。
すると、同じ位数でも置換の位置が変われば、異なるハッシュ値が求められるので、任意の置換の軌道はその置換に固有なものであるということが分かるはずだ。
ファイルの説明:
pace.c:PKP-DSSの奇標数の拡大体バージョン。わざと動かなくしている。
peace.c:PKPで雑音を消して平文を復号するようにしたつもりの暗号。秘密鍵なのに平文が膨らむのを何とかしたい。単にカーネルに含まれるベクトルを平文にかぶせるだけでいいのかも？
sig.c:
秘密のベクトルを$w$とし、更に秘密の置換$Pa$をの逆置換$\inv_Pa$とし、$v[i]=w[inv_Pa[i],x=\sigma(v[P[i]]^v[P[(i+1)%N]])$とし、$v$を公開ベクトル、更に公開置換を$P$とする。
ここで公開鍵は$(P,v,x)$である。
多分この電子署名を最後に暗号からは手を引くと思う。
最後に、PKP-DSSのブラインド署名バージョンを作って終わりたい。
今日も適当に答え合わせして疲れたので動くところでアップロードした。
というか、証明はおろか数式の使い方すらわからない自分が何を言っても伝わらないだろうし、数学のような概念を扱う学問は自分には合わないのだと分かった。
公開しているのは、公開しないとログインできない時にクローン出来なくなるからだ。
出来そうにもないことを趣味にしてしまったのが運の尽きだと思う。
理解するというより、目隠ししながら走り回っているみたいと言われる。
これからはちょっと論理学をやって、数学基礎論（多分無理）を覗いて、Haskellなんかをいじって、自動証明みたいなことをやろうとしたり。
何で論理学かというと、ゼロ知識証明でいうところの健全性とか完全性というのが論理学の用語だと知ったからだ。
これも全て数学の証明の正しさの根拠を理解するためである。
ダメなら歴史の研究とかをやってみたい。 マクニール万歳！ｗ
久しぶりにプログラム。 群論の語の問題を計算するために始めた。 しかし誤の問題を正しく理解していないと計算さえできないので勉強中。 まるで当て外れなことをしているのではないかと気になったけど、外れでもないことが分かり何とかなりそう。 変な方向に行くとしたらちゃんとした知識がないからで、英語の本になるけどネットに落ちていた紙の本だと1万円以上するpdfを読めばいい。
語の問題から新しいテーマは始まる。
組み合わせの生成にcharが使われていて、256以上の次元の置換が生成できなかったところをshortに修正。
いつになったら最新性能のハードの凄さを体感できるのだろうと思っているが、今の流れからすると永遠にその時は来ない気がする。
ブラインド電子署名をやってみたい。
インターネットの匿名性が滅んでいく過程において、仮にその結果が絶滅でも匿名で有り続ける領域を残しておきたい。
匿名性は未来のインターネットにおける可能性の一部だと思っている。
行列って大学数学では基礎なのに、いろんな応用があって凄いと思う。 PKPのランダム公開行列を作れるようになった。
趣味っていうだけあって公開しないということもできるんだけど、パソコンが壊れて予備のメディアもないときに ネットにバックアップがあるのって便利だと思うし、ログインできないときでもクローンできるように公開してるだけって感じ。 なるべくGAFAには頼りたくないし、MSもそのうちだなんだけど、だったらGitLabにもクローン置いとけみたいな。
NIST は、PQC を現在の暗号のように、様々なソリューションやシステムで利用したいと考えており、その
ためには、更なる軽量化が必要であり、2022 年８月に新しいアルゴリズムの公募を開始している。同時に
NIST は、格子アルゴリズムに基づかない新たな追加の汎用署名スキームを公募している。これは、証明書
の透明性などの特定のアプリケーションでは、短い署名と迅速な検証を備えた署名スキームが必要なため
である。
（以下より引用）
https://www8.cao.go.jp/cstp/stmain/pdf/20230314thinktank/seikabutsu/shiryou3-1-02.pdf
余談：今マイブームなのは、秘密計算・ブラインド復号というもので秘密鍵の管理の方法に関係している。 安全でないシステムを安全に使うのは難しいし、秘密鍵だけ安全でも意味がないのだがなんとかできないか。
今日はこのテーマに集中するつもりだったのだが、はじめから挫折。 その後、暗号の安全性理論に興味が移って挫折。
最終的に素体上のパターソン復号にたどり着いた。 誤り位置さえ分かれば決定性アルゴリズムで絵t￥ラーの値を計算できるので、この辺はむやみに多項式をイジる必要がなくなった。 なので今日は寝不足で成果なしである。
素体上ではなく、$F_q:q=3^n$の場合が特に興味深いことがわかる。 ただ公開鍵のサイズが小さくなる利点はあるものの、演算が遅いのが欠点だ。
読めなかった論文が10本近くになった。 これはいかんね。
上にあるCのソースコードは、自分なりに考えたPKPベースの秘密鍵暗号です。 行列部分を符号の生成行列として作りました。 パタリンの効率的なベクトル生成法もあるようなので、それも参考にしたいです。 符号が2次元の正方行列になっているため、符号を超えて行列としても釣っています。 あるいみヒル暗号に近いものがありますが、ヒル暗号のように行列を掛けるだけではなく、 行列の核となるベクトルを選んで、そこに平文を足して、更に符号の生成行列を正則行列として再変換しています。 元の行列が符号語なので、エラーを入れることができるかも知れないですが、復号できるかどうかはまだ確かめていません。 符号語が乱数を代わりを果たしているようにして、そこに平文を足すことで検査行列で符号語を消しつつ、 平文を復元することができました。
まあ何だか色々工夫したはずなんですが、大したことないですね。
本題はこれではなく電子署名なので、まず何に使う電子署名7日を明かしていく作業が必要である。 Fiat-Shamirの動作原理は抱いたわかったので、次はブロックチェーンにブラインド署名を使うことには どういう意味があるのだろうと考えてみたり。
とりあえずこの問題に取り組むことに決めたのはいいんだが、この先余り関心持たないかも。
でも電子署名の安全性を覚えるのにはいい教材のような気がする。
難しい数学は一切なしで、電子署名が作れちゃう！（線形代数は必要です）
そういうときに限ってほとんど関係のないweak popov formなんかの論文が読めてしまったりして戻りたくても引き返せない。 電子署名だけを単独でやろうとするのは動機として弱い気がするので、ここはブロックチェーンを新たに開発する目的で取り組みたい。 チャウミアンコインのような。
本来ここには日記的なことは書かないらしいのだが、私の心の掃き溜めはどこにあるのかしら。 頭のいい人には必ず信者がいるので、私はやはり愚かなのだと確信しつつ暗号技術に磨きをかけたい。
昔の研究テーマの暗号の論文を検索すると、なぜか＊SAの委託研究なんか出てきて、オリジナルのIEEEの論文が出てこない。
最近のネット検索は、人が何を調べているのか情報を集めた上で情報を後出ししてくるみたいで気分が悪い。 欲しい情報が何も得られてないのと同じだからだ。 こういう人為的な情報操作がネットでは可能になってしまう。 つまり、その人が見たいものではなく見せたいものを見せる、あるいは見せたくないものも隠すことができるような不自由なネットだ。 それだけでなく端末上の情報も筒抜けのようになっていて、本当に見せる必要のない自分だけの情報はネットに繋げない端末に保存しないと危ないくらいだ。 いわばテクノロジーの放棄である。 IoTっていらなくね？
結局、人為的な操作が困難な健全な情報源といえば、図書館しかなくなるのだろう。