RSA_theory：RSA的数学原理资源-CSDN文库

：RSA的数学原理

5星 · 超过95%的资源需积分: 9 118 浏览量 2012-01-05 19:25:58 上传评论收藏 92KB PDF 举报

资源推荐

资源详情

资源评论

RSA THEORY

Abstract. This is our proof of the RSA algorithm. There are probably

more elegant and succinct ways of doing this. We have tried to explain

every step in terms of elementary numbe r theory and avoid the ‘clearly

it follows. . . ’ technique favoured by many text books.

1. The Problem

Given positive integers n, e, d such that

n = pq, where p and q are distinct primes(1)

gcd(e, φ(n)) = 1(2)

ed ≡ 1 (mod φ(n))(3)

Deﬁne the public and private key transformations of a message m to be

respectively, for 0 ≤ m < n,

RsaPublic(m) = m

e

mod n(4)

RsaPrivate(m) = m

d

mod n(5)

Prove that, for 0 ≤ m < n,

m = RsaPrivate(RsaPublic(m)) [encryption], and(6)

m = RsaPublic(RsaPrivate(m)) [signature].(7)

2. Basic number theory

We will use these principles of number theory in our proof below.

§1. A prime number is deﬁned as an integer, greater than one, which

only has positive integer divisors (factors) of the number one and

itself. For example, both 7 and 11 are prime but 4 and 9 are not.

§2. Two numbers a and b which have no common factors other than one

are said to be coprime or relatively prime. For example, 4 and 9 are

coprime but 15 and 25 are not.

§3. The greatest common divisor of two integers a and b is the largest

integer that divides both numbers and is denoted by ‘gcd(a, b)’. For

example, gcd(25, 15) = 5 and gcd(4, 9) = 1.

§4. a and b are coprime if and only if gcd(a, b) = 1.

§5. The notation n|a means n divides a (or a is divisible by n) and there

exists an integer d such that a = nd.

§6. If mn|a then m|a and n|a for any integers m, n.

Date: 5 May 2007.

1

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余3页未读，立即下载

内容反馈

zhanghui1094

2014-08-12

东西不错，虽然看起来有点累

wzb56

粉丝: 284
资源: 19

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip