Hatena::ブログ(Diary)

hnwの日記 このページをアンテナに追加 RSSフィード

[プロフィール]
 

2016年11月5日(土) PHPカンファレンス2016でOpenWrtについてLT発表をしました このエントリーを含むブックマーク このエントリーのブックマークコメント

11月3日に開催されたPHPカンファレンス2016でLT発表してきました。以下が発表資料です。



OpenWrtの名前を知ってもらって、その後うっかり触る人が出てきたらいいなあ、と考えて発表してみました。PHPとほとんど関係ない内容でしたが、それなりに面白がって頂けたのかな?と思っています。興味を持った方は「OpenWrt」で検索すれば大体のことは日本語で見つかると思います。また、下記URLで自分がLEDE(OpenWrtのfork)をインストールしたときの手順を紹介しています。



OpenWrtの近況

OpenWrtはルータ向けのLinuxディストリビューションですよ、という程度の紹介をプレゼン中で行いましたが、改めて昨今のOpenWrtを取り巻く状況について書いてみます。


まず、今年の10月にOpenWrt Summit 2016ドイツで開催されました。去年に引き続き2回目の開催のようで、ここに来てプロジェクトとしての勢いが加速しているような印象です。


このOpenWrt Summitをスポンサードしているのがprpl Foundationという組織です。この組織の正体はイマイチわかりませんが、QualcommBroadcomといったMIPS系SoCに関わる大手企業が一定の金を出していそうな雰囲気で、OpenWrt絡みのプロジェクトに出資するような活動もしています(参照:「OpenWrt/LEDE Project Funding Support from prpl」(PDF))。OSSプロジェクトでお財布の心配が無くなることは良いニュースではないでしょうか。


一方で、OpenWrtからLEDEというforkができて大半の開発者が両方にコミットしているような状況でもあり、この人たち本当に大丈夫なのかしら?と思ったりもします。


そんなわけで、OpenWrtは超有望ってほどでもないけど一定期待されているOSSプロジェクトという評価が妥当なのかな、と個人的には考えています。


OpenWrtのバイナリパッケージをTravis CI上でビルドデプロイ

発表では全く触れませんでしたが、OpenWrtのバイナリパッケージのMakefileGitHub上で管理して、git pushすると勝手にTravis CI上でビルドが走ってデプロイまで行われる仕組みを作りました。ビルド環境はDockerイメージとして構築したものをDocker Hubアップロードしています。


f:id:hnw:20161105095911p:image


仕組みの詳細については下記リポジトリの.travis.ymlやTravis CIのログなどをご確認ください。



そもそも、自分専用のパッケージを作るだけであれば手元のマシンでビルドした方が断然楽です。ただ、皆が手元でビルドしているとノウハウの共有が行われにくいので、このように全手順をネット上に公開できる仕組みは価値があると考えています。まだまだ荒削りだと思いますが、参考にして頂ければ嬉しいです。


他のセッションについての感想など

今年のPHPカンファレンスも刺激をたくさんもらった集まりでした。特にt_wadaさんの発表「PHP7で堅牢なコードを書く - 例外処理、表明プログラミング、契約による設計」はスライドもトークも素晴らしいものでした。今回は平行トラック数が多くて見られなかった発表も多かったのですが、興味深いものばかりで、ジャンルとしても多岐に渡っているように感じました。スライドも動画も公開されつつあると思いますので、後で確認したいと思います。


また、懇親会や2次会で多くの方々と技術の話題から雑談まで色々とお話しさせて頂きました。話そうと思っていたのに結局話せなかった方も何人かいらっしゃいましたが、次回こそよろしくお願いいたします。


最後になりますが、発表者の皆様、スタッフの皆様、本当におつかれさまでした。来年も期待しています!

トラックバック - http://d.hatena.ne.jp/hnw/20161105

2016年10月29日(土) PHPでは正規表現コンパイル結果のキャッシュが暗黙に行われている このエントリーを含むブックマーク このエントリーのブックマークコメント

筆者がPHPをさわり始めたころ、「PerlのコレはPHPではどうやるんだろう?」と思うことが頻繁にありました。一部の疑問については解説を見つけたり自分でソースコードを読んだりして解決したものの、考えるのをやめてしまったものもあります。その一つが正規表現コンパイル結果の保存に関するもので、最近まで完全に忘れていました。


正規表現コンパイルというのは与えられた正規表現を解釈して実行しやすいデータ構造に変換する作業のことを指します。具体的にはDFA(決定性有限オートマトン)を構成するか、正規表現エンジン内部で用いられるVM命令列に変換するかといった処理になります。これらは複雑な処理ですので、性能の観点で言えば同じ正規表現に対するコンパイル処理はできるだけ繰り返したくありません。


Perlの場合、スタティックな正規表現コンパイルは1回しか行われません。一方で、正規表現変数が使われている場合は毎回内容が変わる可能性があるため、毎回コンパイルが走ります。毎回のコンパイルを防ぐためのoフラグというものがあるなど、このあたりの仕組みについてはラクダ本でもページ数を割いて説明されており、多くのPerlプログラマ正規表現コンパイルがいつ走るかを意識しながらコードを書いているはずです。


一方、PHPでは正規表現コンパイルに関する話題自体をほとんど聞いたことがないように思います。PHPで同じ正規表現処理が何度も実行される場合に、正規表現コンパイルが1回しか行われないのか、毎回行われているのか、この疑問に答えられるPHPプログラマはごく小数ではないでしょうか。


本稿ではPHP正規表現コンパイルとそのキャッシュの仕組みについて紹介します。


PHPでの正規表現処理


PHP正規表現処理の関数を2系統持っており、それぞれ下記の拡張モジュールで提供されています。


  • PCRE
  • mbstring

PCRE拡張で採用されているPCREはPerl正規表現を提供するライブラリで、他のOSSでの採用事例も多く見られます。PHPでは本家PCREのバージョンアップにマメに追従しており、PHP 7.0.12ではPCRE 8.38が同梱されています。


一方、mbstringは日本では定番のマルチバイト処理の拡張モジュールで、正規表現関数も提供しています。mbstringで利用している正規表現ライブラリRuby 1.9系でも採用されていた鬼車で、PHPに同梱されているのは鬼車 5.9.6です。いまのところ鬼車6.x系への追従や鬼雲に切り替えるなどという話は聞いたことがありません。正直なところ、UTF-8全盛の昨今であればPCREだけで十分な気もします。


ちなみにPHP 5.xまでは更に別のPOSIX正規表現ライブラリも持っていたのですが、7.0からは削除されています。


PCREとコンパイル結果のキャッシュ

まずPCREの方から紹介します。PCRE拡張では正規表現コンパイル結果のキャッシュPHPプロセス内で最大4096個までキャッシュされる仕組みになっています。このキャッシュプロセス内で永続化されているため、正規表現コンパイル結果はリクエストをまたいで共有されます(ただし、プロセスをまたいでの共有はできません)。


最初の疑問について言えば、同じ正規表現が与えられた場合には最初の1回しか正規表現コンパイルは走らないし、もしかすると以前のリクエストで作られたキャッシュにヒットすれば1回も正規表現コンパイルを行わない可能性さえあるというわけです。


実は、このことはPHPマニュアルにも書いてあります。


この拡張モジュールでは、コンパイルした正規表現のためにスレッド単位のグローバルキャッシュ (最大 4096) を管理しています。


http://php.net/manual/ja/intro.pcre.php


このキャッシュの効果は簡単な実験で確認できます。次のようなプログラムを実行してみましょう。


<?php
$num_regex = 4096;
$start = microtime(true);
for ($i = 0; $i < 100; $i++) {
    for ($j = 0; $j < $num_regex; $j++) {
        preg_match("/([a-z]{1,10}){1,10}$j/", "foo");
    }
}
var_dump(microtime(true)-$start);

これは$num_regex種類の異なる正規表現マッチを繰り返し実行するだけのコードで、私の手元で実行したところ0.45秒程度でした。ところが、$num_regexを1増やして4097にしてみると実行時間が18秒となり、劇的に時間がかかるようになってしまいました。正規表現キャッシュサイズが4096であるため、それ以上の種類数にしてしまうと毎回キャッシュが追い出されてしまって都度正規表現コンパイルが走るので非常に遅くなるというわけです。


このキャッシュ処理の詳細はPHPソースコードext/pcre/php_pcre.cのpcre_get_compiled_regex_cache関数で記述されています。


mbstring(鬼車)とコンパイル結果のキャッシュ

mbstringの正規表現コンパイル結果もキャッシュされていますが、こちらは同一リクエスト内のみで使い回され、リクエスト間で共有されることはありません。mbstringではコンパイル結果のキャッシュ個数に上限はなく、異なる正規表現コンパイルするたびにメモリを消費していきます。


また、同じ正規表現で内部的なフラグだけが異なっているような場合は最新1件しかキャッシュされません。つまり、mb_eregとmb_eregiとで同じ$patternを与えたような場合、前に実行した方のコンパイル結果は上書きされてしまい、後で実行した方のキャッシュしか残りません。


このキャッシュ処理はPHPソースコードext/mbstring/php_mbregex.cのphp_mbregex_compile_pattern関数で行われています。


キャッシュに関する注意点

これらのキャッシュ正規表現を理解しているわけではなく、正規表現パターン文字列をキーにしてコンパイル結果を連想配列に格納しているだけです。明らかに同じ内容の正規表現であってもパターン文字列が異なっていればキャッシュは使われず、再度コンパイルが行われます。


たとえば下記のようなコードを書いた場合も、それぞれ個別にコンパイルされてキャッシュエントリを2個消費してしまいます。

<?php
$foo = "foo"
preg_match("/foo/", $foo);
preg_match("~foo~", $foo);

仕組みを考えれば仕方ないかもしれませんが、少し残念ですね。


まとめ

トラックバック - http://d.hatena.ne.jp/hnw/20161029

2016年10月5日(水) PHPプログラムを書いたらマイナス21億行目あたりでエラーが出た このエントリーを含むブックマーク このエントリーのブックマークコメント

(2016/10/5 20:40 追記)誤解を招いている部分がありそうなので文末に補足を追記しました。巨大なプログラムを食わせただけでPHPが死ぬわけではありません。


毎度おなじみ、意図的に重箱の隅をつついてみたよって話です。あるPHPプログラムを実行したら次のようなエラーに遭遇しました。


$ php over-2g-lines.php
int(0)
PHP Fatal error:  Uncaught Error: Call to undefined function var____dump() in /Users/hnw/over-2g-lines.php:2150000004
Stack trace:
#0 {main}
  thrown in /Users/hnw/over-2g-lines.php on line -2144967292

21億5千万4行目で致命的エラーが発生したよ!という表示のあとでスタックトレースが表示されているんですが、スタックトレースの方ではマイナス21.4億行目あたりでエラーが出ていることになっています。行数がマイナスというのは不思議ですね。


種明かしするまでもないと思いますが、原因は32bit整数オーバーフローです。PHPVM命令を管理するzend_op構造体のlinenoメンバは32bit符号無し整数で管理されているため、PHPは43億行目あたりまでしか正確にプログラムの行数をカウントできません。


さらに、printfの修飾子として%dなどとsignedの指定をしている場所があると上のように21.5億あたりでオーバーフローして負数になってしまいます。これはもちろんバグですが、修正したところで誰得な気がします。気が向いたらバグレポを出そうかなと思いつつ、今日はブログ記事にして寝ることにします。


ちなみに上記結果はPHP 7.0.9のものですが、PHP 5系(5.3.0以降)でも大差ないエラー表示になります。


再現方法

手元でも再現したい方のために、実験に使ったPHPプログラムをgistに上げておきました。次のようにすれば元のプログラムを手元に復元できます。


$ curl 'https://gist.githubusercontent.com/hnw/128439edf806daadbdf548b730d67627/raw/over-2g-lines.php.bz2.base64' | base64 -D | bzip2 -cd > over-2g-lines.php

gistに上がっているファイルは2KBほどですが、展開後のPHPファイルは約2GBになりますので、テキストエディタなどで開くと確実に大惨事です。ご注意ください。


ちなみにPHPファイルの内容は以下の通りです。


<?php


/* (21億5千万行の空行) */


$x=0;
var_dump($x);
var____dump($x);

補足というか蛇足というか

21.5億行を超えるPHPプログラムを動かすとPHPがエラーを返すように読み取った方がいるかもしれませんが、そうではありません。巨大なプログラムの後ろの方でわざとエラーを出してみた、というのが上の実験内容です。実際、21億5千万3行目のvar_dump($x)の結果は正しく出力されています(最初の実行結果を参照ください)。21.5億行目から43億行目の間あたりでエラーを起こした場合にエラー表示箇所の行数表示がマイナスになるバグがあるみたい、というのがお伝えしたかった内容でした。


そもそも、古代のBASIC以外のプログラミング言語にとって行数というのは重要なパラメータではなく、エラー発生時に発生箇所をわかりやすく表示するための補助情報に過ぎません。これはPHPにおいても同じで、どれだけ行数の多いプログラムを与えてもそれだけで死ぬことはありません。


もっとも、マトモな処理が21億行書かれたプログラムを与えるとプログラムのparseだけで大量のCPU時間とメモリを消費してしまい、別の理由で死ぬ可能性が高いと思います。これは他の言語でも同じでしょう。

CrazyGoddes VirgoCrazyGoddes Virgo 2016/10/06 21:37 オチはなし

CrazyGoddes VirgoCrazyGoddes Virgo 2016/10/06 21:37 オチはなし

2016年9月18日(日) 続・世界最小のRSA鍵ペアは何bitか このエントリーを含むブックマーク このエントリーのブックマークコメント

前回の記事「世界最小のRSA鍵ペアは何bitか」でp=3, q=5(つまりn=15)の場合のRSA鍵ペアを紹介しましたが、kazuhookuさんからこんなブックマークコメントを頂きました。


面白い。n=4(あるいは2)はダメなのかな


もっと小さいnを採用できないのか?という指摘かと思います。前回記事では普段のRSA暗号のノリで「p,qは異なる奇素数」という前提を置いていましたが、既に非常識なくらい短い鍵長の話をしている中で常識にとらわれるのは無意味というものでしょう。


本稿では15未満のnでRSA暗号らしきものが構成できるのかどうかを探ります。

n=1の場合

RSA暗号の平文mに対して m^(e*d) = m (mod n)が成り立つ最小のnを考えると、n=p=q=e=d=1が見つかります。これは1bit RSA鍵ということになりますので、もし認められるなら世界最小なのは間違いありません。


n=1のRSA暗号というのは、平文も暗号文も0しか無い世界ということになります。文字が一種類しか無い世界での暗号とは何なのか?という哲学的な問いはいったん忘れて、まずはこのような鍵に対してopensslコマンドが動作するのかを調べることにしましょう。


$ cat /tmp/public-key-n1.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAQIBAQ==
-----END PUBLIC KEY-----
$ openssl asn1parse -strparse 17 < /tmp/public-key-n1.pem
    0:d=0  hl=2 l=   6 cons: SEQUENCE
    2:d=1  hl=2 l=   1 prim: INTEGER           :01
    5:d=1  hl=2 l=   1 prim: INTEGER           :01
$ perl -e 'print "\x00"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n1.pem | base64
RSA operation error
140735149846608:error:04068065:rsa routines:RSA_EAY_PUBLIC_ENCRYPT:bad e value:rsa_eay.c:169:

暗号化しようとすると「bad e value」と怒られてしまいました。OpenSSLソースコードを確認したところ、n<=eだとエラーになるようです。これが必須のチェックだとは思いませんが、変な鍵なのは間違いないでしょう。


n=2の場合

次はn=2,e=1が候補になります。同様にOpenSSLで動作確認してみましょう。


$ cat /tmp/public-key-n2.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAgIBAQ==
-----END PUBLIC KEY-----
$ perl -e 'print "\x01"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n2.pem | base64
RSA operation error
140735149846608:error:0306E06C:bignum routines:BN_mod_inverse:no inverse:bn_gcd.c:525:

今度は「no inverse」というエラーで怒られました。どうやら多倍長演算の前準備としてmod nで0x10000000000000000のモジュラ逆数を計算する処理が走るようで、nが偶数だと必ず死ぬようです。OpenSSLバグといえばバグだと思いますが、仕方がないというものでしょう。


n=3の場合

n=3,e=1の場合はどうでしょうか。


$ cat /tmp/public-key-n3.pem
-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBAwIBAQ==
-----END PUBLIC KEY-----
$ perl -e 'print "\x02"' | openssl rsautl -raw -encrypt -pubin -inkey /tmp/public-key-n3.pem | base64
Ag==
$ cat /tmp/private-key-n3.pem
-----BEGIN RSA PRIVATE KEY-----
MBsCAQACAQMCAQECAQECAQMCAQECAQECAQECAQE=
-----END RSA PRIVATE KEY-----
$ echo "Ag==" | base64 -D | openssl rsautl -raw -decrypt -inkey /tmp/private-key-n3.pem | od -tx1 -Ax
0000000    02
0000001

何もトラブルなく動いてしまいました。なんと2bit鍵というわけです。


とはいえ、個人的にはこれをRSA暗号だと言うのには抵抗があります。e=1のときは平文と暗号文が完全に一致するので、そもそも暗号になっていません。


また、RSA暗号ではサイズの大きい合成数nの素因数分解が困難であるということが暗号強度の根拠になっています。しかし、nが素数だとこの前提が崩れてしまい、誰でも秘密鍵を復元できてしまいます。また、公開鍵に含まれるnが素数かどうかはミラー・ラビン素数判定法で高速に判定できるので、攻撃者は弱い鍵を容易に探すことができます。


逆に言うと、nが素数だったりe=1であったりする非常に弱い鍵ペアであってもOpenSSLで正常動作するというのは意外な結果かもしません。


まとめ

  • OpenSSLはnが偶数RSA鍵を想定しておらず、エラー終了する
  • OpenSSLで動作する最小のRSA鍵ペア(らしきもの)はn=3のときである
  • OpenSSLは弱いRSA鍵に対して寛容
トラックバック - http://d.hatena.ne.jp/hnw/20160918

2016年9月11日(日) 世界最小のRSA鍵ペアは何bitか このエントリーを含むブックマーク このエントリーのブックマークコメント

「理論上最短のRSA鍵の鍵長は何ビットなのか?」という疑問が湧いてきたので、RSA鍵の長さに関する制約について調べてみました。とにかく小さいRSA鍵ペアを作ろうと思ったらp=3,q=5の4bit RSA鍵というのが作れそうですが、本当にそんな鍵が作れるのでしょうか?


本稿ではRSA暗号およびRSA署名のパディングに関する仕組みを紹介し、最短の鍵長となるRSA鍵について検討します。


RSAES-PKCS1-v1_5 におけるパディング


鍵長最短となるRSA鍵ペアを作る上で障害になるのが、RSA暗号のパディングと呼ばれる仕組みです。


RSA暗号における暗号化および復号処理は整数の累乗演算ですから、仮に平文mが1だった場合、暗号文も1ということになってしまい暗号として機能しなくなってしまいます。このような問題への対策として、受け取った平文をそのまま使うのではなく、パディング文字列を付加して暗号化するのがRSA暗号では一般的です。復号時には、単にパディング文字列を無視すれば元の平文を取り出せます。


現在もっともよく用いられているRSA暗号の方式は RSAES-PKCS1-v1_5 と呼ばれるもので、与えられた平文にパディングとして固定の3バイトおよびランダムの8バイトを付加します。元の平文が1バイトだとしても計12バイトになってしまうので、RSA暗号が成立するには最低でも96bit必要ということになります。


実際に96bit RSA鍵を作って公開鍵で暗号化してみると、1バイトの平文は暗号化できますが、2バイトの平文を与えると「data too large for key size」と怒られてしまいます。


$ openssl genrsa 96 > private-key.pem
Generating RSA private key, 96 bit long modulus
.+++++++++++++++++++++++++++
..+++++++++++++++++++++++++++
e is 65537 (0x10001)
$ openssl rsa -in private-key.pem -pubout -out public-key.pem
writing RSA key
$ perl -e 'print "a"' | openssl rsautl -encrypt -pubin -inkey public-key.pem | base64
XQRoJI+EJRN73cs9
$ perl -e 'print "ab"' | openssl rsautl -encrypt -pubin -inkey public-key.pem | base64
RSA operation error
140735114489936:error:0406D06E:rsa routines:RSA_padding_add_PKCS1_type_2:data too large for key size:rsa_pk1.c:153:
$

RSA署名だと最短でも368bit鍵が必要

次にRSA署名について考えてみます。署名というのは、対象となる文書ハッシュ値を取り、ハッシュ値RSA秘密鍵暗号化するようなものです。今回は、ハッシュ関数としてSHA1を使うRSASSA-PKCS1-v1_5 with SHA1を考えてみます。


先ほど、RSA 96bit鍵では最長1バイトの平文しか暗号化できないことがわかりました。SHA1は160bitですので、SHA1値をRSA暗号化するのに96bitでは全然足りません。いったいどれほどの長さが必要になるのでしょうか。


調べてみると46バイト(368bit)が最短だとわかりました。パディングの11バイトと、SHA1値の20バイトに加え、ASN.1のヘッダ類で15バイトを消費しますので、これらの合計である46バイトより短い鍵長では署名時にエラーが出てしまいます。実際、360bit鍵でRSA署名を試すとエラーが出ることが分かります。


$ echo foo > foo.txt
$ openssl genrsa 360 > private-key.pem
Generating RSA private key, 360 bit long modulus
.++++++++++++++++++
.....++++++++++++++++++
e is 65537 (0x10001)
$ openssl dgst -sha1 -sign private-key.pem foo.txt
Error Signing Data
140735114489936:error:04075070:rsa routines:RSA_sign:digest too big for rsa key:rsa_sign.c:122:

当然ですが、SHA256などサイズの大きいハッシュ関数を使う場合はより長いRSA鍵が必要になります。


パディング無しで最短のRSA鍵を作る

パディングの存在を考えると、現実の実装が取り扱ってくれそうなRSA鍵は案外長いということがわかりました。では、パディング無しの条件で短い鍵に対する制約があるのでしょうか?


実際にOpenSSLで実験してみることにします。以下はn=15,e=3の公開鍵です。


-----BEGIN PUBLIC KEY-----
MBowDQYJKoZIhvcNAQEBBQADCQAwBgIBDwIBAw==
-----END PUBLIC KEY-----

この鍵で「0x0d」1文字の暗号化を行います。パディング無しにするためopenssl rsautlに「-rawオプションを指定しています。


$ perl -e 'print "\x0d"' | openssl rsautl -raw -encrypt -pubin -inkey shortest-public-key.pem | base64
Bw==

短すぎる暗号文ができました。今度はこれを復号してみます。秘密鍵は下記です。


-----BEGIN RSA PRIVATE KEY-----
MBsCAQACAQ8CAQMCAQMCAQUCAQMCAQMCAQECAQI=
-----END RSA PRIVATE KEY-----

$ echo "Bw==" | base64 -D | openssl rsautl -raw -decrypt -inkey shortest-private-key.pem | od -tx1 -Ax
0000000    0d
0000001

このように、特にトラブルもなく復号できました。4bit RSA鍵での暗号化および復号がOpenSSLで機能したわけです。


補足ですが、この鍵ペアはn=15であるので、15以上の平文・暗号文は扱えません。「0x0f」1文字を暗号化しようとするとエラーで死にます。


$ perl -e 'print "\x0f"' | openssl rsautl -raw -encrypt -pubin -inkey shortest-public-key.pem | base64
RSA operation error
140735114489936:error:04068084:rsa routines:RSA_EAY_PUBLIC_ENCRYPT:data too large for modulus:rsa_eay.c:221:

先ほど紹介したRSAES-PKCS1-v1_5でのパディングの1文字目は0x00になっているのですが、これはnを超える平文を作らせないための仕様なのでしょう。


鍵の強度に関する注意

念のため補足ですが、短いRSA鍵は素因数分解による解読の危険性があります。256bit以下であれば、家庭のPCで一瞬で素因数分解が完了します。512bit鍵も個人が十分解読できる時代です。


2048bit RSA鍵であれば2030年頃までは安全とされていますので、実際に使うのであれば2048bit以上の鍵を使ってください。本稿で紹介した4bit RSA鍵を実用するなどは論外です。


まとめ

  • 世界最小の鍵ペアである4bit RSA鍵がOpenSSLで動作した(全く実用的ではない)
  • 通常の条件であれば暗号化には96bit以上のRSA鍵が、署名には368bit以上のRSA鍵が必要

うめうめ 2016/09/12 21:16 筆算できますかね?

hnwhnw 2016/09/12 22:01 この記事でいう4bit RSAの暗号化および復号処理は15未満の整数の累乗とmod 15の計算だけで構成されるので当然手計算可能ですし、15文字しか無い換字式暗号だと考えれば計算すら必要ないとも言えますね。

hnwhnw 2016/09/12 22:13 鍵長が短ければ筆算によるRSA公開鍵の素因数分解が可能か?という意味であれば当然Yesです。とはいえ、本稿で指摘した通り鍵長が短いとマトモな暗号化ができないので、そのような仮定は厳しいと言えるでしょう。

 
ページビュー
2022859