5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

RSA 暗号を教えて

1 :132人目の素数さん:01/10/10 23:00
ttp://www-robot.mes.titech.ac.jp/staff/takita/ssh/RSA.html
例えばこのページで、
ML mod N = 1 ............(式2)
が成り立つのは分かるけど、これって M と N が互いに素な時だけで
すよね?
だから、 M < N である M に対して、
Cd mod N = (Me mod N)d mod N
= Med mod N (modの性質5より)
= M*(Med-1 mod N) mod N (性質5より)
= M*(M-Lc mod N) mod N (式1より)
= M*((ML mod N)-c mod N) mod N (性質5より)
= M*((1)-c mod N) mod N (式2より)
= M mod N = M (M < N)
は言えないと思うんですけど...

素人のなので、私の勘違いしているところを
指摘してください。

32 : ◆pvySbQO2 :01/10/14 17:00
p,qを異なる素数。
N=pq。

このとき任意の整数Mに対して
M^s≡M(mod.N)
となるならMとして(mod.p)の原始根a
(a^s≡1(mod.p)となる
最小の正の整数sがp−1となるa)をとると
a^s≡a(mod.p)
a^(s−1)≡1(mod.p)
となるのでs−1はp−1の倍数。
s−1はq−1の倍数でもあるので
s−1はp−1とq−1の公倍数になる。

>>25 とあわせて
任意の整数Mに対してM^s≡M(mod.N)
<=>
s−1はp−1とq−1の公倍数。

33 :わしも気になる:01/10/15 02:25
数学に強くないプログラマです。

>>25 さん
> de−1はp−1とq−1の公倍数であればいいので
> L=(p−1)(q−1)としてde≡1(mod.L)としても
> L=lcd(p−1,q−1)としてde≡1(mod.L)としてもいい。

いろいろなRSAの解説(本やWeb)をみてみると、たしかに、φ(n)でよしとしているところと
lcm(p-1, q-1)としているところの両方があります。

で、単に、暗号化したものを復号化できるかどうか、という点で考えれば、
> de−1はp−1とq−1の公倍数であればいいので
は、合っていると思います。

しかし、本家の実装ガイド

 “RSAES-OAEP Encryption Scheme”, RSA Laboratories and RSA Security Inc., 2000,
 ftp://ftp.rsasecurity.com/pub/rsalabs/rsa_algorithm/rsa-oaep_spec.pdf

には、lcm(p-1, q-1)でやれと書いてあります。

きっと理由があるのでしょうが、いったいどうしてなのでしょう。

ひょっとして、暗号強度などに影響するのでしょうか。

34 :132人目の素数さん:01/10/15 06:45
>>33
見れない。

35 :1:01/10/15 10:34
>>33 >>34
http://www.rsasecurity.com/rsalabs/pkcs/pkcs-1/
で見れると思います。

で、lcm(p-1, q-1) に深い理由はないと思いますが?
また暗号強度は p, q の選択だけに依存すると思います
(素因数分解アルゴリズムに対し、強い素数を選ぶ)。

36 :132人目の素数さん:01/10/15 19:43
>>33
35のかたが書いたように、φ(n)とLCM(p-1, q-1)とは暗号強度が変わりません。
そうすると考えられる理由は、あなた(プログラマ)の側にあります。
p,qによってはφ(n)よりLCM(p-1,q-1)のほうがいくらか小さい数(同値で無いなら1/2以下)となるので、
複合する時の計算時間が、多少短くなります。
どれほど短くなるかは、あなたのほうがずっと詳しいでしょ?

37 :33 = Key Generationだけの担当者:01/10/16 02:47
> 36 さん
> どれほど短くなるかは、あなたのほうがずっと詳しいでしょ?
スマヌ、勉強不足じゃあ!!!!

ところで。
> 35 さん
> (素因数分解アルゴリズムに対し、強い素数を選ぶ)。
素因数分解アルゴリズムに対し、強い素数というのがあるのですか。
単純にでかい素数なら良いと思っていたのですが...

あー勉強不足。

38 :37:01/10/16 02:50
> 単純にでかい素数
もちろん、Rabin-Miller witnessなどによる「素数らしきもの」ってことですが...

39 :132人目のポラードさん:01/10/16 08:21
例えば、p-1, q-1 の素因数が小さいような p,q はマズイっすね。

40 :1:01/10/16 08:37
>>37
>>39 の方が言っているように、最低 p-1 の素因数が小さいぐ
らいはチェックするのが普通ですよ。

あと PKCS#1 ver2.1 では multiprime っていう方法もあります。
従来の n = p * q を、n = p1 * p2 * p3 ... ってできます。
512 bit RSA では 2 個まで(すなわち MultiPrime の適用不可)、
1024 - 2048 bit RSA では 3 個の素数まで、安全性を落とすこ
となく使用可能です。この素数の個数は既知の素因数分解アルゴリ
ズムとの兼ね合いから算出されます。
MultiPrime を使うと、CRT の利用により、復号化の計算時間の短
縮が可能となります。
でもこの技術ってコンパックが特許持ってるみたいだから、許可な
しには使えないのかな?その辺のことは良く分かんないですけど。

ところで >>37 さんは、暗号のプログラムを作ってるんですか?

41 :1:01/10/16 08:38
>>40
間違えた、素因素が大きいこと、だった

42 :132人目の素数さん:01/10/16 08:41
>>39
ポラードさんの説明 キボーン!
なぜpでなくp-1(の素因数)が問題となるの?
サイトの紹介(できれば日本語)も歓迎デス!

43 :37:01/10/17 15:43
> 40さん
> ところで >>37 さんは、暗号のプログラムを作ってるんですか?
つくる予定なので調査、勉強してます。

> 42
> なぜpでなくp-1(の素因数)が問題となるの?
秘密指数dが小さくなるからのような気がします(気がするだけです。誰か教えてー)。

実際に、dを求める以前に、dが小さくなりそうな気配を察知する方法ってないものでしょうか。
私も説明キボーン!

44 :1:01/10/18 15:39
>>42 >>43
素因数分解アルゴリズムに対して強い素数を作るためです。
p - 1 が大きな素因数を持てば (p - 1) 法という素因数
分解アルゴリズムに対して、強い素数になるからです。

>>43
そうですか、これからやるんですか。もしかして私が
前に勤めていた会社の人かも?って思ったので...
d が小さくなりそうな気配って、どういう意味で言っ
てるんでしょう?
あと公開指数 e は自分で好きに選べるので、普通 3
とか 65537 使いますよ。ただ 3 選ぶと p, q 選ぶ
のが大変になってしまうので 65537 の方がいいでし
ょう。なので、それにより d も自然に決まります。

45 :37:01/10/18 20:44
>1 さん
どうもありがとうございます。

> d が小さくなりそうな気配って、どういう意味で言っ
> てるんでしょう?

鍵を生成する途中においては、dを計算する前に、すでにpやqが決定されている
わけですよね。そこで、実際に逆元を計算する前に、pやqの特徴をしらべることによって、
dが小さくなってしまわないかどうかを安い計算コストで事前に確認できないかな…と(笑)

…すいません、くだらない話を振ってしまってm(__)m

46 :1:01/10/19 13:58
>>45
ed = k(p-1)(q-1) + 1
なので、e = 65537 とすれば d は十分大きくなると
(小さいという定義がよく分からないのですが)、思
うのですが?
おおよそ、1024 ビットの鍵なら、d のビット数は、
1024 - 17(e のビット数) = 1007 ビット
ってなるんじゃないでしょうか?

47 :132人目の素数さん:01/11/08 17:03
違う話でスマソなんですが、DSAの話でわからないので
教えて下さい。

p,q:素数、p1 mod q
Z/pZ の乗法群の位数qの部分群の生成元を求める時に
「適当にg∈(Z/pZ)^* を取ったとき、g^((p-1)/q)mod p≠1ならば
gの生成する群の位数はqになる」って本に書いてあったのが
よくわからないです。p-1 がq^2で割り切れる時に上手くいかない
ように思うんですが。q^2|p-1 なんてp,qが大きければ滅多な事では
起こらないんでしょうけど少し気になったので。

48 :132人目の素数さん:01/11/08 20:23
>p,q:素数、p≡1 mod q
>Z/pZ の乗法群の位数qの部分群の生成元を求める時に
pが素数だったら部分群なんてないじゃん。

49 :132人目の素数さん:01/11/08 20:52
>>47
「gの生成する群の位数はqで割り切れる」の間違いと思われ。
これならp-1 がq^2で割り切れても成立。

50 :補足:01/11/08 20:55
(p-1 がq^2で割り切れない場合でも)#<g>=qとなるとは限らない。

51 :132人目の素数さん:01/11/08 22:10
>>48(・∀・)

52 :132人目の素数さん:01/11/09 16:52
>>49-50
レスどうもです。確かに、位数がqの倍数であることしか
言えませんね。この後の話で#<g>=qとなることを
使っているので、gの求め方が間違ってるみたいです。

gが#<g>=qを満たすかどうか簡単に判定する方法は
あるのでしょうか?

53 :132人目の素数さん:01/11/09 17:40
g^((p−1)/q)(!早j1(mod.p)のとき
g^((p−1)/q)の生成する群の位数はq。

54 :132人目の素数さん:01/11/09 22:01
>>53
g が Z/pZ の乗法群を生成する場合を考えてみ.
g^( (p-1) /q ) !≡ 1 mod p で、g の生成する
群の位数は p-1.

55 :132人目の素数さん:01/11/09 22:50
>>54
だから何。

56 :132人目の素数さん:01/11/09 22:59
>>53
なるほど。q乗して1になるようにしてしまえば良いんですね。
すっきりしました。ありがとうございます。

57 :132人目の素数さん:01/11/09 23:48
>>53-54
具体的な数字をあたえんとぴんとこないみたいダヨ。
p=5,q=2,g=3のときg^(p-1)/q=3^(5-1)/2=3^2=9!≡1 (mod 5)
だけどg=3の類の生成は生成元だからその生成する群の位数は4≠2=q。

58 :132人目の素数さん:01/11/10 00:10
>>57
そのとき(3^2)^2曹P(mod.5)だから
4の生成する群の位数は2。

59 :132人目の素数さん:01/11/10 00:36
>>58
ああ、g^(p-1)/qの位数か。スマ。でも
p=5,q=2,g=4でおかしいよ。3^(5-1)/4=3!≡1(mod 5)だけど
4の類の位数は4じゃないっしょ。

60 :132人目の素数さん:01/11/10 01:02
>>59
>4の類の位数は4じゃないっしょ。

4じゃないからいいんですけど…。位数qの部分群が
欲しいので、p=5,q=2 の時は位数2の群になって
くれないといけないわけですから。

61 :132人目の素数さん:01/11/10 01:17
>>60
あら、またまちがった。
p=5,q=4,g=4でおかしいよ。4^(5-1)/4=3!≡1(mod 5)だけど
4の類の位数は4じゃないっしょ。
のつもりだった。g^(p-1)/q!≡1(mod p)はq=p-1、g!≡1(mod p)
でつねに成立するけどg!≡1(mod p)で位数q=p-1でないのは
いくらでもあるといいたい。

62 :132人目の素数さん:01/11/10 01:20
>>61
それ、qが素数じゃないです。

63 :132人目の素数さん:01/11/10 01:20
g^((p−1)/q)(!早j1(mod.p)なので
g^((p−1)/q)の生成する群の位数は1ではない。
(g^((p−1)/q))^q曹P(mod.p)なので
g^((p−1)/q)の生成する群の位数はqの約数。
qは素数なのでg^((p−1)/q)の生成する群の位数はq。

64 :132人目の素数さん:01/11/10 01:24
>>62
えっqって素数なの?ほんとだ。>>47に素数ってかいてある。ならおけです。スマ。

65 :132人目の素数さん:01/11/28 09:38
話の腰を折って悪いですが...

x(mod m) の逆元 x^-1(mod m)が既知のとき、x^-1(mod (m - 1)) を簡単に計算する方法
って無いんでしょうか。

ふしぎなことに、xが3のときに限っては、3^-1(mod (m - 1)) = m - (3^-1(mod m))にな
るようなのですが...

66 :65:01/11/28 09:43
<xが3のときの例>

3^-1(mod 123707) = 41236 です。このとき、3^-1(mod 123706) は?

答え: 123707 - 41236 = 82471 です。

67 :132人目の素数さん:01/11/28 09:48
>>65
何故に逆元?

68 :132人目の素数さん:01/11/30 23:41
>>66
んーそれは代表元をそれぞれ 0≦a<m , 0≦b<m-1 で取ってるからですね。
しかも逆元が存在する為の条件 m≡2(mod3)が必須。で、
3^-1の mod m 代表元 a は、 a = (m+1)/3
3^-1の mod m-1 代表元 b は、 b = {2(m-1)+1}/3
でもって、b = m-a と。

69 :                    :01/12/10 02:02
RSA暗号の特許は切れてしまったようですね。

70 :132人目の素数さん:01/12/15 20:19
暗号の強度を計算することは出来るんですか?

71 :132人目の素数さん:01/12/18 13:58
>>70
暗号の強度って?

72 :132人目の素数さん:01/12/26 18:18
RSA の本が発売されるようです。
ttp://books.softbank.co.jp/bm_detail.asp?sku=4797317027

73 :132人目の素数さん:02/01/24 15:51
>>72
俺でも書ける

74 :132人目の素数さん:02/01/24 16:15
最強の暗号は
深谷の手書き文字かな

75 :132人目の素数さん:02/02/04 14:01



76 :そのとき、電波が走った:02/02/04 14:25
RSA信号

77 :132人目の素数さん:02/02/04 15:23
>>74
禿同

78 :132人目の素数さん:02/02/04 16:15
RSA := ラブラブ・シンジ&アスカ(エヴァ板より)

79 :132人目の素数さん:02/02/12 00:37
>>70-71
「計算の複雑性」で定義できるんじゃ?

80 :132人目の素数さん:02/02/12 03:09
>>74
ワロタ
>>78
それを言うならLAS

81 :132人目の素数さん:02/03/30 00:20


27 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.02 2018/11/22 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)