rsa加密算法python_rsa加密算法题目

RSA加密，请问如何用Python实现该加密过程

import random def (a, b):

rsa加密算法python_rsa加密算法题目

while b != 0:

a, b = b, a % b

return a def multiplicative_inverse(e, phi):

d = 0

x1 = 0

x2 = 1

y1 = 1

temp_phi = phi

while e > 0:

temp1 = temp_phi/e

temp2 = temp_phi - temp1 e

temp_phi = e

e = temp2

x = x2- temp1 x1

y = d - temp1 y1

x2 = x1

x1 = x

d = y1

y1 = y

if temp_phi == 1:

return d + phi

'''

Tests to see if a number is prime.

'''

def is_prime(num):

if num == 2:

return True

if num < 2 or num % 2 == 0:

return False

for n in xrange(3, int(num0.5)+2, 2):

if num % n == 0:

return False

return True

def generate_keypair(p, q):

if not (is_prime(p) and is_prime(q)):

raise ValueError('Both numbers must be prime.')

elif p == q:

raise ValueError('p and q cannot be equal')

#n = pq

n = p q

#Phi is the totient of n

phi = (p-1) (q-1)

#Choose an integer e such that e and phi(n) are coprime

e = random.randrange(1, phi)

#Use Euclid's Algorithm to verify that e and phi(n) are comprime

g = (e, phi)

while g != 1:

e = random.randrange(1, phi)

g = (e, phi)

#Use Extended Euclid's Algorithm to generate the private key

d = multiplicative_inverse(e, phi)

#Return public and private keypair

#Public key is (e, n) and private key is (d, n)

return ((e, n), (d, n))

def encrypt(pk, plaintext):

#Unpack the key into it's components

key, n = pk

#Convert each letter in the plaintext to numbers based on the character using a^b mod m

cipher = [(ord(char) key) % n for char in plaintext]

#Return the array of bytes

return cipher

def decrypt(pk, ciphertext):

#Unpack the key into its components

key, n = pk

#Generate the plaintext based on the ciphertext and key using a^b mod m

plain = [chr((char key) % n) for char in ciphertext]

#Return the array of bytes as a string

return ''.join(plain)

if __name__ == '__main__':

print "RSA Encrypter/ Decrypter"

p = int(raw_input("Enter a prime number (17, 19, 23, etc): "))

q = int(raw_input("Enter another prime number (Not one you entered above): "))

print "Generating your public/private keypairs now . . ."

public, private = generate_keypair(p, q)

print "Your public key is ", public ," and your private key is ", private

message = raw_input("Enter a message to encrypt with your private key: ")

encrypted_msg = encrypt(private, message)

print "Your encrypted message is: "

print ''.join(map(lambda x: str(x), encrypted_msg))

print "Decrypting message with public key ", public ," . . ."

print "Your message is:"

print decrypt(public, encrypted_msg)

密码学基础1：RSA算法原理全面解析

本节内容中可能用到的符号说明如下：

质数和合数： 质数是指除了平凡约数1和自身之外，没有其他约数的大于1的正整数。大于1的正整数中不是素数的则为合数。如 7、11 是质数，而 4、9 是合数。在 RSA 算法中主要用到了质数相关性质，质数可能是上帝留给人类的一把钥匙，许多数学定理和猜想都跟质数有关。

[定理1] 除法定理： 对任意整数 a 和 任意正整数 n，存在的整数 q 和 r，满足 。其中， 称为除法的商，而 称为除法的余数。

整除： 在除法定理中，当余数 时，表示 a 能被 n 整除，或者说 a 是 n 的倍数，用符号 表示。

约数和倍数 ： 对于整数 d 和 a，如果 ，且 ，则我们说 d 是 a 的约数，a 是 d 的倍数。

公约数： 对于整数 d，a，b，如果 d 是 a 的约数且 d 也是 b 的约数，则 d 是 a 和 b 的公约数。如 30 的约数有 1，2，3，5，6，10，15，30，而 24 的约数有 1，2，3，4，6，8，12，24，则 30 和 24 的公约数有 1，2，3，6。其中 1 是任意两个整数的公约数。

公约数的性质：

公约数： 两个整数的公约数称为公约数，用 来表示，如 30 和 24 的公约数是 6。 有一些显而易见的性质：

[定理2] 公约数定理： 如果 a 和 b 是不为0的整数，则 是 a 和 b 的线性组合 中的小正元素。

由定理2可以得到一个推论：

[推论1] 对任意整数 a 和 b，如果 且 ，则 。

互质数： 如果两个整数 a 和 b 只有公因数 1，即 ，则我们就称这两个数是互质数(coprime）。比如 4 和 9 是互质数，但是 15 和 25 不是互质数。

互质数的性质：

欧几里得算法分为朴素欧几里得算法和扩展欧几里得算法，朴素法用于求两个数的公约数，而扩展的欧几里得算法则有更多广泛应用，如后面要提到的求一个数对特定模数的模逆元素等。

求两个非负整数的公约数有名的是 辗转相除法，早出现在伟大的数学家欧几里得在他的经典巨作《几何原本》中。辗转相除法算法求两个非负整数的公约数描述如下：

例如， ，在求解过程中，较大的数缩小，持续进行同样的计算可以不断缩小这两个数直至其中一个变成零。

欧几里得算法的python实现如下：

扩展欧几里得算法在 RSA 算法中求模反元素有很重要的应用，定义如下：

定义： 对于不全为 0 的非负整数 ，则必然存在整数对 ，使得

例如，a 为 3，b 为 8，则 。那么，必然存在整数对 ，满足 。简单计算可以得到 满足要求。

扩展欧几里得算法的python实现如下：

同余： 对于正整数 n 和 整数 a，b，如果满足 ，即 a-b 是 n 的倍数，则我们称 a 和 b 对模 n 同余，记号如下： 例如，因为 ，于是有 。

对于正整数 n，整数 ，如果 则我们可以得到如下性质：

譬如，因为 ，则可以推出 。

另外，若 p 和 q 互质，且 ，则可推出：

此外，模的四则运算还有如下一些性质，证明也比较简单，略去。

模逆元素： 对整数 a 和正整数 n，a 对模数 n 的模逆元素是指满足以下条件的整数 b。 a 对 模数 n 的 模逆元素不一定存在，a 对 模数 n 的模逆元素存在的充分必要条件是 a 和 n 互质，这个在后面我们会有证明。若模逆元素存在，也不是的。例如 a=3，n=4，则 a 对模数 n 的模逆元素为 7 + 4k，即 7，11，15，...都是整数 3 对模数 4 的模逆元素。如果 a 和 n 不互质，如 a = 2，n = 4，则不存在模逆元素。

[推论2] 模逆元素存在的充分必要条件是整数 a 和 模数 n 互质。

[定理3] 质数分解定理： 任何一个大于1的正整数 n 都可以 分解 为一组质数的乘积，其中 都是自然数(包括0)。比如 6000 可以分解为 。

由质数分解定理可以得到一个推论： 质数有无穷多个 。

[定理4] 剩余定理(Chinese remainder theorem，CRT) ，早见于《孙子算经》(南北朝数学著作，公元420-589年)，叫物不知数问题，也叫韩信点兵问题。

翻译过来就是已知一个一元线性同余方程组求 x 的解：

宋朝数学家秦九韶在他的著作中给出了物不知数问题的解法，明朝的数学家程大位甚至编了一个《孙子歌诀》：

意思就是：将除以 3 的余数 2 乘以 70，将除以 5 的余数 3 乘以 21，将除以 7 的余数 2 乘以 15，终将这三个数相加得到 。再将 233 除以 3，5，7 的小公倍数 105 得到的余数 ，即为符合要求的小正整数，实际上， 都符合要求。

物不知数问题解法本质

求解通项公式

剩余定理相当于给出了以下的一元线性同余方程组的有解的判定条件，并用构造法给出了解的具体形式。

模数 两两互质 ，则对任意的整数： ，方程组 有解，且解可以由如下构造方法得到：

并设 是除 以外的其他 个模数的乘积。

剩余定理通项公式证明

如何用python用私钥给报文rsa加密

近要跟某支付接口对接,在服务端这边,要求对数据进行签名,而他们提供的demo是ja的

PrivateKey pKey = (PrivateKey)store.getKey(alias, pwd.toCharArray());

Cipher cipher = Cipher.getInstance("RSA/ECB/PKCS1Padding");

cipher.init(Cipher.ENCRYPT_MODE, pKey);

其中- - pkey 他们是用私钥的 ,一般来说不是用公钥加密私钥解密吗.而且,签名是签名,加密是加密吧- - 怎么他们说要我去签名,但他们实际却是用私钥去加密来充当签名 --

现在我这边是用python,但是模拟他们的操作后发现加密后结果并不一样,感觉有点乱了

python:

with open(UNIONPAY_PRIVATE_KEY_FILE) as key_file:

key2 = rsa.PrivateKey.load_pkcs1(key_file.read())

msg8 = msg.encode('utf-8')

msg_dis = md5(msg8).digest()

print rsa.encrypt(msg_dis,key2)

print b64encode(rsa.encrypt(msg_dis,key2))

怎么用 python 模拟 js 里 JSEncrypt 模块的加密方式

PC登录新浪微博时，在客户端用js预先对用户名、密码都进行了加密，而且在POST之前会GET一组参数，这也将作为POST_DATA的一部分。这样，就不能用通常的那种简单方法来模拟POST登录（比如人人网）。

用python怎么实现RSA签名

from Crypto.Signature import PKCS1_v1_5 as pk

privatekey=RSA.importKey(open('pkcs8_rsa_private_key.pem','r').read())

def sign(self,signdata):

'''

@param signdata: 需要签名的字符串

'''

h=SHA.new(signdata)

signer = pk.new(privatekey)

signn=signer.sign(h)

signn=base64.b64encode(signn)

return signn

一般是这么写的， 但是我得的key是个字符串， 怎么转成pkcs8格式

如何用python用私钥给报文rsa加密

mod是一种整数之间的相互运算，就是通常所说的取余数运算。例如：2187mod20=7就表示2187除以20，余数是7.更常见的表示方法是2187=7(mod20)注意这里的等号通常都写成恒等号（就是三横，我这里打不出恒等号）。相应地读作2187与7关于模（即mod)20同余。关于同余有一套比较完整的理论，这是数论里的内容，本题只需要一些比较基础的数论知识。一般来讲，公开密钥系统的公钥都是取两个大素数。对这两个大素数进行一系列的运算，详细的内容可以参考百科。本题里由于d与n，e与n互素，所以也可算。本题就是对消息m=3的加密。利用公钥以及加密方法即得密文=m^e对n=20取模。结果就是3^7=2187=7(mod20).反过来，现在得到了密文7，那么利用解密密钥d=3就知道原文m=(密文)^3=7^3=343=3(mod20),也就是原文是3.