RSA加密算法简记

λ posted @ 2011年9月05日 13:40 in Algorithm with tags arithmetic , 5926 阅读

基於大素數分解的困難性,解密算法用歐拉定理得證。

初始化工作

1. 取兩個大素數:$p,\ q,\ (p \ne q)$

2. $n = pq,\ \Phi (n) = (p-1)(q-1)$

3. 取正整數 $w$ ,$\mathrm{gcd}(w,\ \Phi (n)) = 1$

3. 求 $w$ 的模 $\Phi (n)$ 逆 $d$ ,即有 $dw \equiv 1 (\mathrm{mod}\ \Phi (n))$

4. 將明文數字化,並分成多段,每段的值 $m$ 小於 $n$ 。

加密

$c = E(m) = m^w\ \mathrm{mod}\ n$

解密

$m = D(c) = c^d\ \mathrm{mod}\ n$

 

公鑰:$w,\ n$

私鑰:$p,\ q,\ \Phi (n),\ d$

 


附快速模冪運算方法

$a^b\ \mathrm{mod}\ n$

設 $b$ 的二進製表示為 $b_{r-1}\ldots b_{1}b_{0}$,即有

$b = b_{0} + b_{1}\times 2 + \cdots + b_{r-1}\times 2^{r-1}$

於是

$a^b \equiv a^{b_0} \times (a^2)^{b_1} \times \cdots \times (a^{2^{r-1}})^{b_{r-1}} (\mathrm{mod}\ n)$

令 $A_0 = a,\ A_i \equiv A_{i-1}^2 (\mathrm{mod}\ n),\ i = 1, 2, \cdots , r-1$ ,則有

$a^b \equiv A_0^{b_0} \times A_1^{b_1} \times \cdots \times A_{r-1}^{b_{r-1}} (\mathrm{mod}\ n)$

上面,$A_i^{b_i} = \begin{cases}A_i,\ 若\ b_i = 1\\1,\ 若\ b_i = 0\end{cases}\quad i = 0, 1, \cdots , r-1$

 


本網站無註明「轉載」的著作均由Jak Wings製作 CC BY-NC-SA 2.5
Creative Commons 保持署名-相同方式分享 2.5

  • 无匹配
  • 无匹配
New India Assurance 说:
Aug 07, 2022 07:04:20 PM

New India Assurance corporation limited does offer insurance plans for vehicles which include commercial vehicles and private vehicles. The insurance policy does protect them from third-party liabilities and unwanted expenses which might arise through accidental damage or due to any kind of loss to the vehicle. New India Assurance Online Payment Having proper insurance will cover your entire vehicle damage as per their insured value, as well having regular insurance will help you have good value as it gets changed every year with a calculated percentage.

Uttarakhand Board 8t 说:
Aug 16, 2022 08:19:08 PM

Uttarakhand Board Model Paper 2023 Class 8 Pdf Download with Answers for English Medium, Hindi Medium, Urdu Medium & Students for Small Answers, Long Answer, Very Long Answer Questions, and Essay Type Questions to Term1 & Term2 Exams

lalitha jewellery sc 说:
Oct 27, 2022 04:08:09 PM

Lalithaa Jewellery is a rare sophisticated, and unique Company in India. The Gold business was established in 1985 by Kiran Kumar in Chennai, Tamil Nadu and now operates in various states in India (Karnataka, Pondicherry, Andhra Pradesh, and Telangana). lalitha jewellery scheme online payment The Company offers quality Jewellery collections at affordable prices. The collections are pretty rare, making Lalithaa the best Jewellery dealer in the country.

ITR Login 说:
Dec 25, 2022 06:16:46 PM

Everyone who is an employee or has a tax to pay to the government knows about Income Tax returns which are favorable term coined for the people by the government. ITR Login Every year during a certain period, all people are allowed to apply for their income tax returns by submitting various proofs, documents, and papers related to their money transactions that can help them get their tax returns back easily.

12th Blueprint 2024 说:
Feb 13, 2023 03:56:18 PM

Board of Secondary Education has deferred the Class 12th board Exam should be held from May 2024. The candidates can check the Class 12th Board blueprint Papers from true site. 12th Blueprint 2024 The 12th Question Paper 2024 will likewise be reported on class 12th students can take note of the total 12th Exam Pattern 2024. Download the Board Model Paper and Question Paper 2024 as indicated by the 12th Class Model Paper 2024 educational board.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter