草庐IT

RSA 基本思路如下

runoob 2023-03-28 原文

1.公钥与私钥的生成：

  • (1) 随机挑选两个大质数 p 和 q，构造n = p*q;
  • (2)计算欧拉函数φ(n) = (p-1) * (q-1);
  • (3)随机挑选e，使得gcd(e, φ(n)) = 1，即 e 与 φ(n) 互素,gcd指的是求最大公约数;
  • (4)计算d，使得 e*d ≡ 1 (mod φ(n))，即d 是e 的乘法逆元。

2.加密过程：

  • (1)待加密信息（明文）为 m，m < n；（因为要做模运算，若m大于n，则后面的运算不会成立，因此当信息比n要大时，应该分块加密）;

  • (2))密文 c 的生成是 $$ c = m^e mod (n) $$

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$

3.解密

$$ c^d mod (n) = (m^e)^d mod (n) = m^(d*e) mod (n) ; $$

为什么能解密？

要用到欧拉定理（其实是费马小定理的推广）

a^φ(n) ≡ 1 (mod n)，

再推广：a^(φ(n)k) ≡ 1 (mod n)，

得到 a^(φ(n)k+1) ≡ a (mod n)

注意到 ed ≡ 1 mod φ(N)，即：ed = 1 + k*φ(N)。

因此，$$ M^(de) mod N = M^1 + kφ(N) mod N = M $$

4.代码如下

实例



#coding=utf-8
#__author__ = 'ralph'
import random
 
def extendedGCD(a, b):
    #a*xi + b*yi = ri
    if b == 0:
        return (1, 0, a)
    #a*x1 + b*y1 = a
    x1 = 1
    y1 = 0
    #a*x2 + b*y2 = b
    x2 = 0
    y2 = 1
    while b != 0:
        q = a / b
        #ri = r(i-2) % r(i-1)
        r = a % b
        a = b
        b = r
        #xi = x(i-2) - q*x(i-1)
        x = x1 - q*x2
        x1 = x2
        x2 = x
        #yi = y(i-2) - q*y(i-1)
        y = y1 - q*y2
        y1 = y2
        y2 = y
    return(x1, y1, a)
 
def computeD(fn, e):
    (x, y, r) = extendedGCD(fn, e)
    #y maybe < 0, so convert it
    if y < 0:
        return fn + y
    return y
 
def keyGeneration(p,q,e):
    #generate public key and private key
    n = p * q
    fn = (p-1) * (q-1)
    d = computeD(fn, e)
    return (d,n)
 
p_v = int(raw_input('请输入p的值(10进制)\n'))
q_v = int(raw_input('请输入q的值(10进制)\n'))
e_v = int(raw_input('请输入e的值(10进制)\n'))
c_v = int(raw_input('请输入密文c的值(10进制)\n'))
 
(d,n) = keyGeneration(p_v,q_v,e_v)  #生成 d和n
 
m = pow(c_v,d,n)
print ("得到的明文m是: "+str(m))

当输入p值：18443，q值：49891，e值19，

密文c值：

70479679275221115227470416418414022368270835483295235263072905459788476483295235459788476663551792475206804459788476428313374475206804459788476425392137704796792458265677341524652483295235534149509425392137428313374425392137341524652458265677263072905483295235828509797341524652425392137475206804428313374483295235475206804459788476306220148

得到的结果就会显示

得到的明文m是: 88455713

RSA基本spanclasshl-code

有关RSA 基本思路如下的更多相关文章

  1. Unity 热更新技术 | （三） Lua语言基本介绍及下载安装 - 2

    ?博客主页：https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创，首发于CSDN??学习专栏推荐：Unity系统学习专栏?游戏制作专栏推荐：游戏制作?Unity实战100例专栏推荐：Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正！?未来很长，值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  2. 计算机毕业设计ssm+vue基本微信小程序的小学生兴趣延时班预约小程序 - 2

    项目介绍随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱小学生兴趣延时班预约小程序的设计与开发被用户普遍使用,为方便用户能够可以随时进行小学生兴趣延时班预约小程序的设计与开发的数据信息管理,特开发了小程序的设计与开发的管理系统。小学生兴趣延时班预约小程序的设计与开发的开发利用现有的成熟技术参考,以源代码为模板,分析功能调整与小学生兴趣延时班预约小程序的设计与开发的实际需求相结合,讨论了小学生兴趣延时班预约小程序的设计与开发的使用。开发环境开发说明：前端使用微信微信小程序开发工具：后端使用ssm：VU

  3. ruby-on-rails - 使用 HTTParty 的非常基本的 Rails 4.1 API 调用 - 2

    Rails相对较新。我正在尝试调用一个API，它应该向我返回一个唯一的URL。我的应用程序中捆绑了HTTParty。我已经创建了一个UniqueNumberController，并且我已经阅读了几个HTTParty指南，直到我想要什么，但也许我只是有点迷路，真的不知道该怎么做。基本上，我需要做的就是调用API，获取它返回的URL，然后将该URL插入到用户的数据库中。谁能给我指出正确的方向或与我分享一些代码？ 最佳答案 假设API为JSON格式并返回如下数据:{"url":"http://example.com/unique-url"

  4. ruby-on-rails - Ruby - 如何从 ruby​​ 上的 .pfx 文件中提取公钥、rsa 私钥和 CA key - 2

    我有一个.pfx格式的证书，我需要使用ruby​​提取公共(public)、私有(private)和CA证书。使用shell我可以这样做:#ExtractPublicKey(askforpassword)opensslpkcs12-infile.pfx-outfile_public.pem-clcerts-nokeys#ExtractCertificateAuthorityKey(askforpassword)opensslpkcs12-infile.pfx-outfile_ca.pem-cacerts-nokeys#ExtractPrivateKey(askforpassword)o

  5. ruby-on-rails - Rails 基本 Base64 身份验证 - 2

    我正在尝试复制此GETcurl请求:curl-D--XGET-H"Authorization:BasicdGVzdEB0YXByZXNlYXJjaC5jb206NGMzMTg2Mjg4YWUyM2ZkOTY2MWNiNWRmY2NlMTkzMGU="-H"Content-Type:application/json"http://staging.example.com/api/v1/campaigns在Ruby中，通过电子邮件+apikey生成身份验证:auth="Basic"+Base64::encode64("test@example.com:4c3186288ae23fd9661c

  6. Simulink方法总结和避坑指南（一）——Simulink入门与基本调试方法 - 2

    文章目录一、项目场景二、基本模块原理与调试方法分析——信源部分：三、信号处理部分和显示部分：四、基本的通信链路搭建：四、特殊模块：interpretedMATLABfunction：五、总结和坑点提醒一、项目场景  最近一个任务是使用simulink搭建一个MIMO串扰消除的链路，并用实际收到的数据进行测试，在搭建的过程中也遇到了不少的问题（当然这比vivado里面的debug好不知道多少倍）。准备趁着这个机会，先以一个很基本的通信链路对simulink基础和相关的debug方法进行总结。  在本篇中，主要记录simulink的基本原理和基本的SISO通信传输链路（QPSK方式），计划在下篇记

  7. ruby - 是否有 Rack::Session::Cookie 用法的基本示例？ - 2

    我找不到任何使用Rack::Session::Cookie的简单示例，并且希望能够将信息存储在cookie中，并在以后的请求中访问它并让它过期.这些是我能找到的唯一示例:HowdoIset/getsessionvarsinaRackapp?http://rack.rubyforge.org/doc/classes/Rack/Session/Cookie.html这是我得到的:useRack::Session::Cookie,:key=>'rack.session',:domain=>'foo.com',:path=>'/',:expire_after=>2592000,:secret=

  8. ruby - 具有基本身份验证和 gzip 的 em-http 流挂起 - 2

    我正在尝试使用GnipPowerTrackAPI，这需要我使用基本身份验证连接到JSON的HTTPS流。我觉得这应该是相当微不足道的，所以我希望一些比我聪明的ruby​​ist可以指出我明显的错误。这是我的ruby​​1.9.3代码的相关部分:require'eventmachine'require'em-http'require'json'usage="#{$0}"abortusageunlessuser=ARGV.shiftabortusageunlesspassword=ARGV.shiftGNIP_STREAMING_URL='https://stream.gnip.com:4

  9. ruby - 从 Ruby 打开 RSA 私钥 - 2

    我认为我知道如何创建自定义的加密RSAkey，但我如何才能像ssh-keygen那样读取一个加密的key？我知道我可以做到:OpenSSL::PKey::RSA.new(File.read('private_key'))但是OpenSSL要求我提供密码...我如何将它作为参数传递给OpenSSL？而且，我如何创建一个与ssh-keygen生成的兼容的？我做这样的事情来创建私有(private)加密key:pass='123456'key=OpenSSL::PKey::RSA.new(1024)key="0000000000000000#{key.to_der}"c=OpenSSL::C

  10. micropython复现经典单片机项目（二）可视化音频 频谱解析（基本搞定） - 2

    本人是音乐爱好者，从小就特别喜欢那个随着音乐跳动的方框效果，就是这个：arduino上一大把对，我忍你很久了，我就想用mpy做，全网没有，行我自己研究。果然兴趣是最好的老师，我之前有篇博客专门讲音频，有兴趣的可以回顾一下。提到可视化频谱，必然绕不开fft，大学学过这玩意，当时一心玩，老师讲的一个字都么听进去，网上教程简略扫了一下，大该就是把时域转频域的工具，我大mpy居然没有fft函数，奶奶的，先放着。音频信息如何收集？第一种傻瓜式的ADC，模拟转数字，原始粗暴，第二种，I2S库，我之前博客有讲过，数据是PCM编码。然后又去学PCM编码，一学豁然开朗，舒服，以代码为例：audio_in=I2S

随机推荐