RSA暗号のアルゴリズム - 版の履歴

Wiki: /* 安全性 */

2021-05-23T01:03:37Z

安全性

← 古い版		2021年5月23日 (日) 10:03時点における版
50行目:		50行目:
	<br>		<br>
	* 復号できる理由		* 復号できる理由
	*: 暗号化：<math>~~mk_1\,~~\bmod\,n</math>		*: 暗号化：<math>m^{k_1} \bmod n</math>
	*: 復号　：<math>~~Ck_2\,~~\bmod\,n</math>		*: 復号　：<math>C^{k_2} \bmod n</math>
	<br>		<br>
	証明<br>		証明<br>

Wiki: /* メッセージを受け取る側の復号方法 */

2021-05-23T00:52:03Z

メッセージを受け取る側の復号方法

← 古い版		2021年5月23日 (日) 09:52時点における版
40行目:		40行目:

	===== メッセージを受け取る側の復号方法 =====		===== メッセージを受け取る側の復号方法 =====
	~~暗号文Cと秘密鍵k~~<sub>2</sub>~~を用いて、~~<math>~~Ck_2\,~~\bmod\,n</math>~~を計算すると、~~<br>		受信した暗号文Cと秘密鍵k<sub>2</sub>を使用して復号する時、以下の式から求められる。<br>
			<math>M = C^{k_2} \bmod n</math><br>
			<br>
	これが元のメッセージに一致する。(後述)		これが元のメッセージに一致する。(後述)
	<br>		<br>

	===== 安全性 =====		===== 安全性 =====
	暗号文Cと公開鍵n、k<sub>1</sub>が分かっても、(現実的な時間では)mを復元することはできない。<br>		暗号文Cと公開鍵n、k<sub>1</sub>が分かっても、(現実的な時間では)mを復元することはできない。<br>

Wiki: /* メッセージを送る側の暗号化方法 */

2021-05-23T00:48:53Z

メッセージを送る側の暗号化方法

← 古い版		2021年5月23日 (日) 09:48時点における版
34行目:		34行目:

	===== メッセージを送る側の暗号化方法 =====		===== メッセージを送る側の暗号化方法 =====
	~~送りたいメッセージをm(~~ただし、<math>0 \le m \le n</math>~~を満たす)とする。~~<br>		送信するメッセージをMとする時、暗号文をCは、以下の式で求められる。<br>
	~~公開鍵を用いて~~<math>~~mk_1\,~~\bmod\,n</math>~~を計算し、これを暗号文(Cとおく)とする。~~<br>		ただし、<math>\,0 \le M \le n \,</math>を満たす。<br>
			<math>C = M^{k_1} \bmod n</math><br>
	<br>		<br>

	===== メッセージを受け取る側の復号方法 =====		===== メッセージを受け取る側の復号方法 =====
	暗号文Cと秘密鍵k<sub>2</sub>を用いて、<math>Ck_2\,\bmod\,n</math>を計算すると、<br>		暗号文Cと秘密鍵k<sub>2</sub>を用いて、<math>Ck_2\,\bmod\,n</math>を計算すると、<br>

Wiki: /* RSA暗号の仕組み */

2021-05-23T00:41:36Z

RSA暗号の仕組み

← 古い版		2021年5月23日 (日) 09:41時点における版
13行目:		13行目:
	== RSA暗号の仕組み ==		== RSA暗号の仕組み ==
	* 公開鍵		* 公開鍵
	*: n : 2つの素数の積		** n : 2つの素数の積
	*: k<sub>1</sub> : <math>\phi(n) = (p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub>		** k<sub>1</sub> : <math>\phi(n) = (p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub> (ただし、<math>1 < k_{1} < n</math>を満たすこと)
	* 秘密鍵		* 秘密鍵
	*: 素数p		** 素数p
	*: 素数q		** 素数q
	*: φ(n) : <math>(p - 1)(q - 1)</math>の積		** φ(n) : <math>(p - 1)(q - 1)</math>の積
	*: k<sub>2</sub> : <math>k_1k_2 \equiv 1 \bmod (p - 1)(q - 1)</math>となるk<sub>2</sub>		** k<sub>2</sub> : <math>k_1k_2 \equiv 1 \bmod (p - 1)(q - 1)</math>となるk<sub>2</sub>
	<br>		<br>
	===== メッセージを受け取る側の準備 =====		===== メッセージを受け取る側の準備 =====

Wiki: /* 前提知識 */

2020-03-06T20:26:31Z

前提知識

← 古い版		2020年3月7日 (土) 05:26時点における版
6行目:		6行目:
	以下の初等整数論の知識を用いる。<br>		以下の初等整数論の知識を用いる。<br>
	<br>		<br>
	* 合同式の基礎		* [[合同式の基礎]]
	* フェルマーの小定理		* [[フェルマーの小定理]]
	* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>		* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>
	<br><br>		<br><br>

Wiki: /* RSA暗号の仕組み */

2020-03-06T14:53:25Z

RSA暗号の仕組み

← 古い版		2020年3月6日 (金) 23:53時点における版
12行目:		12行目:

	== RSA暗号の仕組み ==		== RSA暗号の仕組み ==
			* 公開鍵
			*: n : 2つの素数の積
			*: k<sub>1</sub> : <math>\phi(n) = (p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub>
			* 秘密鍵
			*: 素数p
			*: 素数q
			*: φ(n) : <math>(p - 1)(q - 1)</math>の積
			*: k<sub>2</sub> : <math>k_1k_2 \equiv 1 \bmod (p - 1)(q - 1)</math>となるk<sub>2</sub>
			<br>
	===== メッセージを受け取る側の準備 =====		===== メッセージを受け取る側の準備 =====
	大きな素数pとqを生成して、<math>n = pq</math>とする。<br>		大きな素数pとqを生成して、<math>n = pq</math>とする。<br>

Wiki: /* メッセージを受け取る側の準備 */

2020-03-06T14:43:57Z

メッセージを受け取る側の準備

← 古い版		2020年3月6日 (金) 23:43時点における版
14行目:		14行目:
	===== メッセージを受け取る側の準備 =====		===== メッセージを受け取る側の準備 =====
	大きな素数pとqを生成して、<math>n = pq</math>とする。<br>		大きな素数pとqを生成して、<math>n = pq</math>とする。<br>
	<math>(p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub>を取る。<br>		<math>\phi(n) = (p - 1)(q - 1)</math>と互いに素な整数k<sub>1</sub>を取る。<br>
	<math>k_1k_2 \equiv 1\,\bmod\,(p - 1)(q - 1)</math>となるk<sub>2</sub>を取る。<br>		<math>k_1k_2 \equiv 1\,\bmod\,(p - 1)(q - 1)</math>となるk<sub>2</sub>を取る。<br>
	<br>		<br>
23行目:		23行目:
	* k<sub>2</sub>は非公開にする(秘密鍵)		* k<sub>2</sub>は非公開にする(秘密鍵)
	<br>		<br>

	===== メッセージを送る側の暗号化方法 =====		===== メッセージを送る側の暗号化方法 =====
	送りたいメッセージをm(ただし、<math>0 \le m \le n</math>を満たす)とする。<br>		送りたいメッセージをm(ただし、<math>0 \le m \le n</math>を満たす)とする。<br>

Wiki: /* 前提知識 */

2020-03-06T14:38:47Z

前提知識

← 古い版		2020年3月6日 (金) 23:38時点における版
6行目:		6行目:
	以下の初等整数論の知識を用いる。<br>		以下の初等整数論の知識を用いる。<br>
	<br>		<br>
	* [[合同式の基礎]]		* 合同式の基礎
	* [[フェルマーの小定理]]		* フェルマーの小定理
	* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>		* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>
	<br><br>		<br><br>

Wiki: /* 前提知識 */

2020-03-06T14:37:25Z

前提知識

← 古い版		2020年3月6日 (金) 23:37時点における版
6行目:		6行目:
	以下の初等整数論の知識を用いる。<br>		以下の初等整数論の知識を用いる。<br>
	<br>		<br>
	* 合同式の基礎		* [[合同式の基礎]]
	* フェルマーの小定理		* [[フェルマーの小定理]]
	* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>		* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。<br>
	<br><br>		<br><br>

Wiki: ページの作成:「== 概要 == 公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について記載する。

== 前提知識 ==…」

2020-03-06T12:10:57Z

ページの作成:「== 概要 == 公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について記載する。 == 前提知識 ==…」

新規ページ

== 概要 ==
公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について記載する。 
 

== 前提知識 ==
以下の初等整数論の知識を用いる。 
 
* 合同式の基礎
* フェルマーの小定理
* 有名な定理 : aとbが互いに素なとき、<math>ax \equiv 1\,\bmod\,b</math>となるxが、<math>1 \le x \le b - 1</math>の間でただ1つ存在する。 
 

== RSA暗号の仕組み ==
===== メッセージを受け取る側の準備 =====
大きな素数pとqを生成して、<math>n = pq</math>とする。 
<math>(p - 1)(q - 1)</math>と互いに素な整数k1を取る。 
<math>k_1k_2 \equiv 1\,\bmod\,(p - 1)(q - 1)</math>となるk2を取る。 
 
'''※注意''' 
'''上記の有名な定理により、<math>0 \le k_2 \le (p - 1)(q - 1)</math>とすると、k2は一意に定まる。''' 
'''また、ここまでの操作は高速にできることが知られている。''' 
* nとk1を公開する(公開鍵)
* k2は非公開にする(秘密鍵)
 
===== メッセージを送る側の暗号化方法 =====
送りたいメッセージをm(ただし、<math>0 \le m \le n</math>を満たす)とする。 
公開鍵を用いて<math>mk_1\,\bmod\,n</math>を計算し、これを暗号文(Cとおく)とする。 
 
===== メッセージを受け取る側の復号方法 =====
暗号文Cと秘密鍵k2を用いて、<math>Ck_2\,\bmod\,n</math>を計算すると、 
これが元のメッセージに一致する。(後述)
 
===== 安全性 =====
暗号文Cと公開鍵n、k1が分かっても、(現実的な時間では)mを復元することはできない。 
 
* 復号できる理由
*: 暗号化：<math>mk_1\,\bmod\,n</math>
*: 復号　：<math>Ck_2\,\bmod\,n</math>
 
証明 
<math>m^{k_1k_2} \equiv m\,\bmod\,n</math>を証明すればよい。 
<math>m^{k_1k_2} \equiv m\,\bmod\,p</math>を証明すれば十分である。(対称性より、<math>\bmod q</math>も同様) 
 
mがpの倍数のとき、両辺ともにpの倍数よりOK。 
mがpの倍数でないとき、<math>k_1k_2 - 1</math>が<math>p - 1</math>の倍数となるように設定したので、 
整数Nを用いて、<math>k_1k_2 = 1 + N(p - 1)</math>とおける。 
よって、<math>m^{k_1k_2} = m * (m^{p - 1})N \equiv m * 1^N \bmod n= m</math>となる。 
(ただし、途中の<math>\equiv</math>は<math>\bmod n</math>であり、フェルマーの小定理を用いた) 
 

== RSA暗号の安全性と素因数分解 ==
素因数分解が簡単に(短時間で)計算できれば、RSA暗号は破られる。 
 
* RSA暗号が破られる理由 
*: 暗号文C、公開鍵k1、nは誰でも見ることができる。
*: ここで、nを素因数分解することでpとqが求まる。
*: すると、"メッセージを受け取る側の準備"と同じ方法で秘密鍵k2が求まり、元のメッセージMを復号できる。
 

__FORCETOC__
[[カテゴリ:暗号理論]]

RSA暗号のアルゴリズム - 版の履歴

Wiki: /* 安全性 */

Wiki: /* メッセージを受け取る側の復号方法 */

Wiki: /* メッセージを送る側の暗号化方法 */

Wiki: /* RSA暗号の仕組み */

Wiki: /* 前提知識 */

Wiki: /* RSA暗号の仕組み */

Wiki: /* メッセージを受け取る側の準備 */

Wiki: /* 前提知識 */

Wiki: /* 前提知識 */

Wiki: ページの作成:「== 概要 == 公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について記載する。 == 前提知識 ==…」

Wiki: ページの作成:「== 概要 == 公開鍵暗号方式の具体的なアルゴリズムであるRSA暗号の仕組みと安全性について記載する。

== 前提知識 ==…」