Nim and RSA(7)

『海外出張』(ダイヤモンド社)なんて本を読んだ。副題に、成功の鍵はホテルにあり！なんて付いていた。リタイアしたオイラーには、もう不要なはずなのに。

100歩ゆずったとしても、現役時代、ホテルにこだわる事なんてしなかったなあ。寝れれば、そして安全であれば、それでOKって主義でしたから。

本書はそれを否定してる。ビジネスマンこそ、ホテルにこだわるべき。どんな核の所に宿泊してるかが、ステータスになるからと。りっぱな身なりをするのと一緒。そして、ホテルの機能を十分に引き出してこそ、ビジネスを成功に導く秘訣とも。

ビジネスセンターで、通訳を雇ったり、印刷したり、フィットネス・クラブでリフレッシュしたり出来るのは、安いBBのホテルでは出来ませんよと。それって、トレンディードラマに出て来る、きむたくさんみたいだな。

付録で、便利なホテルでの会話集が付いていた。

The Computer froze, and I can't even reboot.

パソコンがフリーズして、再起動も出来ません。出来るビジネスマンがこんな事で、おろおろするかね？そんなん、うむを言わせず、電源断だろうに。言われたホテルの人は、どう対処するんだろう？オタクを設備してるのだろうか？

オイラーが一流ホテルに泊まって、嬉しかったのは、北京の外資系ホテルだったかなあ。暇を持て余して、案内を見てたら、レンタサイクル有りますって出てた事。いくらチャリの国と言っても、市中で貸し自転車屋を探すのは、それだけでくたびれてしまいそう。

さっそく、チャリと地図を手に、市中へ繰り出しましたよ。目的は買い物。出発前に、こんな物を買いたいんだけど、どこら辺に行けばいいって、聞いておいた。

広大な天安門広場を眺めながら、古びた町並みに行きましたねぇ。中国4000年の歴史のある所っぽい所で、買い物が出来て、Gooooooodでしたよ。

あと、りっぱなホテルではないけど、居心地が良かったのは、ドイツの片田舎のBBなホテル。ベッドと朝食提供のホテルね。あそこの朝食が口に合ってたたなあ。

丸パンをナイフでスライスして、よりどりみどりのハムを挟んで食べるやつ。パンの種類もハムの種類も豊富なものだから、いろいろな組み合わせにトライ。飽きる事なかった。

そのホテルにレストランが併設。村の社交場みたいになってて、いろいろな人と知り合いになれた。むこうからしたら、変なやつが居るぞ。どこから来たんか聞いてみよー。何、ヤーパンから来たって。ゲイシャは居るんか？どんな着物を着てるんか？遠い国だったんすね。

RSAを使う

前回、tccとMD5の組み合わせが不調だったので、種を駄洒落で作ってみたい。語呂合わせとか、16進数なら、 Hexspeak や AからFだけで構成される英単語から、見繕ってくればいいだろう。あなたの知性が試されますよ。毎度、893(やくざ）や、 abadcaff(まずいコーヒー）じゃつまらないですから。

人に頼らずに自分で調べてみれ

[sakae@fb10 /usr/share/dict]$ grep -E '^[a-fA-F][a-f][a-f]+$' words | wc
      96      96     493

4文字以上だと65語になった。これだけあれば十分かな。

ともあれGMPとの合わせ技で、結構使えるものになった。キャメルケースを平気で読める、あの言語族の人は不満がないだろう。

var M = "I Like Nim Python Lisp Scheme Clojure Ruby 4649"
var a, c : mpz
echo "\n", M
var m = init_mpz(M, 62)
echo "m: ", m
mpz_powm(c, m, e, n)
echo "c: ", c
mpz_powm(a, c, d, n)
echo "a: ", a
discard mpz_out_str(stdout, 62, a)
echo " "

実行してみると、

I Like Nim Python Lisp Scheme Clojure Ruby 4649
m: 2368801101545695871182130052235878863748308303555837537712476700143769
c: 111573458711461238479456273468498663050240486042737182473673056859119978325
a: 2368801101545695871182130052235878863748308303555837537712476700143769
ILikeNimPythonLispSchemeClojureRuby4649

ここで、一つ注意すべき事が有る。まずは、実例を

seed: 3d747b1c55b23a
p: 3744634287414685577791
q: 3522120437025564111443
n: 13189052952889924215703582329132453969762413
e: 65537
d: 6967938255349813632669625256699315913816833

I Like Nim Python Lisp Scheme Clojure Ruby 4649
m: 2368801101545695871182130052235878863748308303555837537712476700143769
c: 7765033156190690279623766764713074631171388
a: 4175684821740848355722850210294213291052596
Os5lAM65FecC7gfEB41oFgpg

暗号キーの一部である n と、平文を数値に変換した m の間には、m<n という関係が無いと、正しく暗号化出来ないという制限が有るんだ。素数夜曲の本でも、強く警告してたな。それは何故か？

暗号化するには、キーをe 及びnとすると、m^e mod n の計算を行っているから (^は、冪乗記号)。結果は必ず、n 以下に丸められてしまう。m>=nだと、情報欠落になってしまうんだ。

日本語もRSA暗号出来るようにする

素数夜曲に出て来るRSAでは、平文をASCII文字列と仮定している。ASCIIってアメリカ生まれの文字コードね。それがそのままISOになったのだけど、国際標準規格にアメリカって名前は無いだろうってんで、ISOなんたらって規格番号に変身してるんだ。昔アメリカは強かったけど、国名を冠するのは国際社会に受け入れられなかったのね。

そういう例がまだ他にも有ったぞ。地球時間を表す、GMT。これもイギリスのグリニッジ地方のローカル時間。これって、イギリスの栄光をそのまま現していて癪にさわるぞって、どこかの国が言い出すに決まってる。それを回避するため、UTCなんて名前になってる。政治ですなあ。

最近では、赤い国が言い出した世界銀行もどきのやつ。AIIBとか称して、これからの注目はアジアですよって強調してる。シルクロードを新たに作って、沿線住民とデストネーションを豊かにしましょってやつ。北陸新幹線が開通して豊かになるのは、デストネーションだけですよ。でも、そういう事は言わない約束です。

話が逸れた。ASCIIコードは、0から127までに文字を割り振った体系。数字、英文字、各種記号がもれなく網羅されててもそれだけの数で済んじゃう、国の人の体系です。この中には、印刷出来ない、いわゆる制御文字も含まれている。

暗号の最終目的地は、人間が読み書き出来る文字なんで、制御文字はイラネって考えると、イラネって文字と取り除いちゃえって発想が出てくる。上手に取り除けば、100個に満たない数値で、文字を表せるぞ。そうなれば、いわゆる100進法が適用出来て便利。

コード表をじっと眺めていたら、ASCIIコードから27を引く事を思い付いた。SHIFT-JISならぬ SHIFT-ASCIIの発明ですな。その取り繕いをSchemeのコードで実現してたぞ。面白い。

ひるがえって、日本語の平文を暗号にするのはどうよ？いっぱい文字があり過ぎて、小手先の手段では、簡単にいかないな。ええい、コードを書いちゃえ。

その前に実行結果をば。

[sakae@fedora gmp]$ ./rsa
seed: 23237b1c55b23a46499696893be
n: 240523885418313615330947131716914414586821803528652295824687766884361857089
size: 31
e: 65537
d: 90305182181104182657632865755625007012182979313106412327496075053220922785
こんにちわ世界
Keyを逆に使う

実行例に出て来るsizeってのは、この文字数までなら（但し、ASCII文字ね）暗号化出来ますって目安です。こちらがコード。

## RSA using GMP

import gmp
import gmp/utils
import strutils

let e: mpz = 65537
var p, q, n, phi, d : mpz
var seed = "23237b1c55b23a46499696893be"
echo "seed: ", seed

mpz_nextprime(p, init_mpz("caff" & seed, 16))
mpz_nextprime(q, init_mpz("abad" & seed, 16))
mpz_mul(n, p, q)
#echo "p: ", p
#echo "q: ", q
echo "n: ", n
echo "size: ", mpz_sizeinbase(n, 16) div 2

mpz_sub(p, p, 1)
mpz_sub(q, q, 1)
mpz_mul(phi, p, q)
mpz_gcdext(p, d, q, e, phi)
if d < 0:
    mpz_add(d, d, phi)
echo "e: ", e
echo "d: ", d

proc encode*(msg: string, e: mpz, n: mpz) : mpz =
    var s = ""
    var i = msg.high
    while i >= 0:
        s.add(toHex(ord(msg[i]), 2))
        dec(i)
    var m = init_mpz(s, 16)
    if n <= m:
        quit("Msg too long", 1)
    var c : mpz
    mpz_powm(c, m, e, n)
    return c

proc decode*(c: mpz, d: mpz, n: mpz) : string =
    result = ""
    var a, h : mpz
    mpz_powm(a, c, d, n)
    while 0 < a:
        mpz_mod(h, a, 256)
        result.add(chr(parseInt($h)))
        mpz_tdiv_q(a, a, 256)

when isMainModule:
    var M = "こんにちわ世界"
    var c =  encode(M, e, n)
    echo decode(c, d, n)

    M = "Keyを逆に使う"
    c =  encode(M, d, n)
    echo decode(c, e, n)

平文と公開鍵を受け取って、暗号数値に変換するencodeと、暗号数値と秘密鍵を受け取って、平文に復元するdecodeって関数を定義したよ。 when以下は、その用例。キーは、逆に使っても大丈夫。いわゆる認証にどうぞってやつだ。

まずはencodeの方。文字列はbyteの連なり。byteってのは0から255まで表せるASCIIの拡張ね。これを、ord関数を使って数値に変換。それを2文字分の16進数にtoHexを使って変換。そいつを、溜め込んでいく。この時、byteのスキャンを逆にやってるのは、decodeする時の都合です。

こうして、16進文字列に変換出来たら、後は、それをGMPに備わっている関数でGMP用の数値に変換、暗号化すればよい。数値に変換した時、キーの大きさより大きかったら、諦めてもらう。

decodeの方は、ます暗号数値を復号。それを文字列に戻していく。256で割れば、1byte分を取り出せる。それはGMP風の出力なんでparseIntで普通のIntに直し、それをchrで文字と言うか byteに直している。

下位の桁から文字に確定して行くので、逆転した文字列になるはずなんだけど、encodeで逆にscanしてたから、辻褄が合って、上位から確定してる事になる。

後は、256で割った商を取り出して、商が0になるまで上記を繰り返す。この時、商を求める関数に最初、mpz_cdiv_q を使っていたんだ。そしたら、永久ループさ。いつまで経っても、商が１になるんだ。いわば、23/256の商が１になるんだ。慌てて、GMPのマニュアルを見ましたよ。

cdiv rounds q up towards +infinity, and r will have the opposite sign to d. The c stands for “ceil”.
fdiv rounds q down towards -infinity, and r will have the same sign as d. The f stands for “floor”.
tdiv rounds q towards zero, and r will have the same sign as n. The t stands for “truncate”.

割り算には商の丸め方によって3種あるとな。cdivは、大きい方に向かって丸めちゃうんで、結果が１になっちゃうと判明。tdivを使って事なきを得ましたよ。あっ、事が有ったからこういう事を知ったんじゃん。日本語の使い方を間違ってますな。詳細な事は、 5.6 Division Functions を参照。いろいろ有って、目がチカチカするぞ。

で、今ふと思ったんだけど、tdivを使ったりmodを使ったり随分とGMPに頼っているな。 GMPの数値を16進数へと変換出来れば、後はnimの世界だけで事が済むぞ。直交演算はきっとあるはず。こういう時は、gmp/utils.nimの中を眺めるに限る。

お目当ての関数は、＄さ。

proc `$`*(a: mpz_t, base: cint = 10): string =
  result = newString(mpz_sizeinbase(a, base) + 1)
  return $mpz_get_str(result,base,a)

何気なく使うやつに、省略時のデフォルトが設定されてた。

let x: mpz = 1024
echo x $ 16
echo ($(x))

実行結果は

400
1024

ふーむ、文字数が奇数になる場合がある事に注意せいとな。

日本語って大変だ

とまあ、無事に日本語も暗号・復号出来るようになったけど、日本海海戦で打たれた有名な電文、「敵艦見ユトノ警報ニ接シ連合艦隊ハ直チニ出動コレヲ撃滅セントス、本日天気晴朗ナレドモ波高シ」は、そんなの長すぎって言われて、暗号文にならない。これは困った。日本負けちゃう、一大事ですよ。景気の良いトラトラトラぐらいは暗号に出来るかな？って、これを暗号にしたって意味ねーじゃん。

ってな事は置いておいて、日本語の表現をちょいと調べてみる。

import strutils
import unicode

let m = "The日本国"

proc MruneLenAt*(s: string, i: Natural): int =
  ## returns the number of bytes the rune starting at ``s[i]`` takes.
  if ord(s[i]) <=% 127: result = 1
  elif ord(s[i]) shr 5 == 0b110: result = 2
  elif ord(s[i]) shr 4 == 0b1110: result = 3
  elif ord(s[i]) shr 3 == 0b11110: result = 4
  elif ord(s[i]) shr 2 == 0b111110: result = 5
  elif ord(s[i]) shr 1 == 0b1111110: result = 6
  else: result = -1  # almost 0b10xxxxxx

echo runeLen(m)
echo len(m)

for i in 0 .. high(m):
    stdout.write MruneLenAt(m, i), ", "
echo "\n"
for i in 0 .. high(m):
    stdout.write toHex(ord(m[i]), 2), ", "
echo "\n"

世界の文字コード、ユニコードをサポートするのが当たり前になってるな。表現は UTF-8が当然のごとく使われている。

6
12
1, 1, 1, 3, -1, -1, 3, -1, -1, 3, -1, -1,

54, 68, 65, E6, 97, A5, E6, 9C, AC, E5, 9B, BD,

ASCII以外は、多Byteで文字を表現してねってのを、あの人が発明した。そしてその文字表現を ASCII以外って表現出来ないものだから、やんわりとRuneなんて言い方で誤魔化した。

Runeって辞書で引くと、スカンジナビアの古詩、フィンランドの詩歌、ルーン文字、詩歌、神秘的な記号、北欧古代文字とか出てきて、幻想的だな。決してASCII以外とは、取らないように。米中心の排他主義を必死で隠そうと、苦労したんだからー。

米国からみると、十羽一束にされちゃった文字だけど、文字数ぐらいは数えられるようにしてあげようってんで、runeLenとかがサポートされてる。元を質せばバイトの寄せ集め。バイト列を見ていった時に、どこが文字の始まりかを教えてくれる、runeLenAtがサポートされてたけど、文字を構成する要素の場合も１を返すようになってた。

そこで、ちょいと手を入れて、文字を構成する要素の場合は、－１を返すようにした。そんなんで、日本語文字は、３Byteで１文字になってるのが分かるな。

RASを安全に

コンピュータの進歩によりRSAの鍵長を大きくする事が推奨されている。昔は1024Bitも有れば安全とされていたのに、今じゃ2048Bitを推奨しますですって。

鍵長を大きくするには、鍵を求めるに使う乱数を大きくする必要がある。どうするか？

乱数の一種であるπから得るのがよかろう。him-gmpの使用例として、πをｎ桁求めるアプリが付いてくる。ちょいと実験。

[sakae@fedora gmp]$ ./pin 200
31415926535897932384626433832795028841971693993751      :50
05820974944592307816406286208998628034825342117067      :100
98214808651328230664709384460955058223172535940812      :150
84811174502841027019385211055596446229489549303819      :200

上記は200桁まで表示させたけど、お望みならなん桁までも。数値を適当に貰ってきて、62進法と看做して、桁数を水増しするのが正しい方法です。ちなみに、どれぐらいの桁が水増しされるかと言うと、

gosh> (/ (log 62)(log 10))
1.7923916894982537
gosh> (/ (log 10)(log 2))
3.3219280948873626

62進のｎ桁は、10進数の約1.8倍。10進のｎ桁は、2進数の3.32倍に相当する。

var seed = "31415926535897932384626433832795028841971693993751"
mpz_nextprime(p, init_mpz("feed" & seed, 62))

2048Bitにしても、256Byte相当。これで日本語Rune文字を表現しようとすると、85文字しか暗号化できません。なかなか大変ですな。sslとかを噛ませて、暗号方式は共有鍵方式を使うのが、正しい方法です。

nim vs go

nimを始めた時に、ロゼッタストーンなんてのが有ることを知った。そこに登録されてるコードを２つの言語で同時表示させるサイトが有るのね。 Side-by-side code snippets from Rosetta Code

そこで、nimとgoを並べて表示させてみると、 nim vs go nimは、すっきりさっぱりですなあ。更にすっきりさせようと思ったらHaskellをやっとけって結論で宜しいでしょうか。