■ECCがSSLに採用される時代が来た。
「RSA以外の公開鍵暗号を用いた証明書発行サービスは、商用サービスとしては初めて」らしい。
ベリサイン、RSAよりも負荷が軽いECC（楕円曲線暗号）をSSL証明書に採用
http://itpro.nikkeibp.co.jp/article/NEWS/20130214/456308/?top_tl1
■RSAのおもちゃ版。
要件はアルファベットのみ暗号化したいものとする。
ググっても、大抵概念で終わるか、数学か、難しい実装ばかりなので、
おもちゃ版をワンライナーで。
$ echo -n "abcdefghijklmnopqrstuvwxyz" | wc -c
26
■上記は1〜26の数字に割り当てる。
10進⇒16進⇒ASCII変換
http://d.hatena.ne.jp/labunix/20130106
16進⇒10進⇒ASCII変換
http://d.hatena.ne.jp/labunix/20130108
ASCII⇒10進⇒16進変換
http://d.hatena.ne.jp/labunix/20130107
$ echo -n "abcdefghijklmnopqrstuvwxyz" | \
sed s/"."/"&\n"/g | grep -v ^\$ | \
for char in `xargs`;do echo $(printf "%3d" \"$char) | \
awk '{printf "%02d ",$1-96}';done | xargs echo -n;echo
01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
■RSA Step 1
mを平文とする。
p=5,q=11の素数が秘密鍵とする。
pq=55が公開鍵とする。
$ echo "$((5*11))"
55
■「元の数(平文=m),べき乗(n)」の形式のリスト。
最後の27行だけ出力していたり、nkfで横幅を整形している点は気にしない。
気になる方はお気に入りのページャで確認して下さい。
$ for n in `seq 1 $((55/2))`;do \
for m in `seq $((55/2))`;do \
echo "$m,$n"; \
done; \
done | tail -27 | xargs echo -n | nkf -Lu -c -w -f80;echo
1,27 2,27 3,27 4,27 5,27 6,27 7,27 8,27 9,27 10,27 11,27 12,27 13,27 14,27 15,27
16,27 17,27 18,27 19,27 20,27 21,27 22,27 23,27 24,27 25,27 26,27 27,27
■復号鍵をkとする。
「元の数^べき乗数%pq」が元の数になる(復号できる)kを得る。
「27,1」は平文と一致するnを探す。
$ for n in `seq 1 $((55/2))`;do \
for m in `seq $((55/2))`;do \
echo "(mod (expt $m $n) 55)" | clisp -q | grep $m > /dev/null 2>&1 && echo "$m,$n"; \
done; \
done | awk -F, '{print $2}' | uniq -c | grep "27 [0-9]"
27 1
27 21
■上記のように時間をかけなくても n*【(p-1)(q-1)の最小公倍数】+1で求められる。
最小公倍数の公式についてはここでは触れない。
$ echo "(+ (* $((5-1)) $((11-1))) 1)" | clisp -q
[1]>
41
$ echo "(+ (/ (* $((5-1)) $((11-1))) 2) 1)" | clisp -q
[1]>
21
■最小公倍数20より小さく、互いに素なeを適当に決めます。
「互いに素」を含めて、この条件が何を指すかはここでは触れない。
clispで素数と素数の数を得る（1億まで）
http://d.hatena.ne.jp/labunix/20111207
■公開鍵をeとする。
秘密鍵をdとする。
素数と互いに素は異なるので、混乱しないで欲しいが、
以下の素数リストからかけるとkになり、2つを得られる3と7の素数を使う。
$ echo "(defun eratosthenes (n)
(labels ((foo (i ls)
(if (= i 1)
ls
(foo (1- i) (cons i ls))))
(spam (ls0 ls1)
(if (> (expt (car ls1) 2) (car (last ls0)))
(revappend ls1 ls0)
(let ((ls2
(remove-if #'(lambda (x)
(zerop (mod x (car ls1))))
ls0)))
(spam (cdr ls2) (cons (car ls2) ls1))))))
(let ((lst (foo n nil)))
(spam (cdr lst) (list (car lst))))))
(eratosthenes 20)" | clisp -q
[1]>
ERATOSTHENES
[2]>
(2 3 5 7 11 13 17 19)
■暗号文字cを得る。
c = m^e mod pq
d=3
e=7
$ echo "(setq e 7)(setq pq (* 5 11))(setq m 2)(mod (expt m e) pq)" | clisp -q
[1]>
7
[2]>
55
[3]>
2
[4]>
18
■復号化する。
※eとdが2つを得た今回の方法に限り、以下でdが得られる。
k/e=d
m = c^d mod pq
$ echo "(setq c 18)(setq pq (* 5 11))(setq d (/ 21 7))(mod (expt c d) pq)" | clisp -q
[1]>
18
[2]>
55
[3]>
3
[4]>
2
■暗号文「c=*」を得る。
$ echo "Hello World" | tr '[A-Z]' '[a-z]' | sed s/"."/"&\n"/g | grep -v "^\$\| " | \
for char in `xargs` ;do \
echo -n "before m=$char,";m=`echo $(printf "%3d" \"$char) | \
awk '{printf "%2d\n",$1-96}'`;echo -n "m=$m,c="; \
echo "(setq e 7)(setq pq (* 5 11))(setq m ${m})(mod (expt m e) pq)" | clisp -q | tail -1; \
done
before m=h,m= 8,c=2
before m=e,m= 5,c=25
before m=l,m=12,c=23
before m=l,m=12,c=23
before m=o,m=15,c=5
before m=w,m=23,c=12
before m=o,m=15,c=5
before m=r,m=18,c=17
before m=l,m=12,c=23
before m=d,m= 4,c=49
■暗号文を復号する一歩手前。
$ echo "before m=h,m= 8,c=2
before m=e,m= 5,c=25
before m=l,m=12,c=23
before m=l,m=12,c=23
before m=o,m=15,c=5
before m=w,m=23,c=12
before m=o,m=15,c=5
before m=r,m=18,c=17
before m=l,m=12,c=23
before m=d,m= 4,c=49" | awk -F, '{print $3}' | awk -F\= '{print $2}' | \
for c in `xargs`;do \
echo "(setq c 18)(setq pq (* 5 11))(setq d (/ 21 7))(mod (expt ${c} d) pq)" | clisp -q | tail -1; \
done
8
5
12
12
15
23
15
18
12
4
■復号化。
$ echo "before m=h,m= 8,c=2
before m=e,m= 5,c=25
before m=l,m=12,c=23
before m=l,m=12,c=23
before m=o,m=15,c=5
before m=w,m=23,c=12
before m=o,m=15,c=5
before m=r,m=18,c=17
before m=l,m=12,c=23
before m=d,m= 4,c=49" | awk -F, '{print $3}' | awk -F\= '{print $2}' | \
for c in `xargs`;do \
echo "(setq c 18)(setq pq (* 5 11))(setq d (/ 21 7))(mod (expt ${c} d) pq)" | clisp -q | tail -1 | \
awk '{print $1+96}' | awk '{printf "%c",$1}'; \
done;echo
helloworld
