您好、欢迎来到现金彩票网!
当前位置:秒速时时彩开奖 > 算法保密 >

RSA算法以及数学基础

发布时间:2019-06-25 09:32 来源:未知 编辑:admin

  由于传统密钥体制出现了困难,例如2000个用户保密通信每个人需要保存1999个密钥(两两保密通信需要共(2000*19999)/2 = 1999000个密钥,每人保管1999个),在密钥管理分配上有困难。另外由于数字签名(身份认证)的需要增加。

  公钥体制解决了上述两个问题,即每个人有一对密钥(公钥和私钥),将公钥公开,私钥自己保管,这样每人只要保管好自己的私钥就可以了。通信时使用收信方的公钥进行加密,收信方使用私钥进行解密。在身份认证时,签名者使用私钥签名,验证签名者使用签名者的公钥验签。当然在实际应用时还有其他的问题需要保证,例如抗抵赖,保持信息的完整性等密码学问题。在本文中先不考虑。

  有上述公钥体制的任务中我们知道,区别于其他密钥体制算法,公钥算法需要做到的是将加密密钥(公钥)和加密算法公开,破坏者也不能由公钥和密文破译出明文。只有使用解密密钥(私钥)和解密算法才能解出明文。而且保证通过公钥不能推出私钥。

  上述内容可以通过所谓的“单向函数”来实现。(传统的密钥体制中加密算法和解密算法是互逆的。)所谓“单向函数”是指加密函数E和解密函数D。但是已知加密函数E推导其逆运算却非常困难(也就是推导私钥的过程)。所以若不知道解密函数(或私钥)不可能解出明文。

  算数基本定理:任何大于1的整数都可以分解成素数乘积的形式,并且,如果不计分解式中素数的次序,该分解式是唯一的[微软中国1]。

  这个定理在理论上十分漂亮,但是操作起来却非常困难下表列出了现代最快的分解算法在大型计算机上分解一个大数所用的时间。

  1. 一个大于1的整数p,若除1和起本身之外没有其他正整数因数(约数),称P为素数。

  2. 若整数a和b最大公约数为1,则称a,b互素,记为(gcd(a,b)= 1)。

  3. 设n为正整数,a和b为整数,若a和b被n除后所得余数相同,称a和b模n同余,记为a≡b(mod n)。此式被称为同余式。若n能整除a则同余式表示为a≡0(mod n)。

  两个整数模n同余的等价说法有:a和b被n除余数相同。a-b被n整除。a和b在模n的同一个剩余类中。存在整数s使得a=sn+b。

  (3) 若ka≡kb(mod n),且k与n互素时,有a≡b(mod n)。(同余式消去律)

  5. 设n为正整数 ,则任何一个整数被n除 ,余数必为0,1,2,…,n-1中的某一个,把整数集中被n除余数相同的数分别归为一类,记为[0],[1],[2]…,[n-1],这样就按模是否同余把整数集分成n类,其中每一类都称为模n的一个剩余类。显然,每个整数必属于上述类中的一类,被n除余数不同的数必属于上述的不同类中。若a0,a1,a3…,an-1分别取自上述类的不同类中,称a0,a1,a3…,an-1为模n的一个完全剩余系,该剩余系中的数两两模n不同余。

  6. 含有未知量的同余式称为同余方程。一次同余方程是最简单的一种,其一般形式为ax≡b(mod n)。若a,n的最大公约数d能整除b,则ax≡b(mod n)有解。且恰有d个解。若a,n的最大公约数d不能能整除b,则ax≡b(mod n)无解。例如同余方程7x≡1(mod 5)。7与5最大公约数为1,能被b=1整除,故有一个解。7x≡1(mod 5)≡6≡11≡21(mod5)。由于7与5互素有消去律得x=3。.[微软中国3]

  一般地 解同余方程的步骤为 ①判断解的情况 ②当同余方程的a,b,n有公因数时 ,约去公因数化简方程 ③利用同余的定义和消去律求方程的解。

  7. 费马小定理:设任意整数a和素数p互素[微软中国4] ,则ap-1≡1(mod p)。

  给定一个正整数p,任意一个整数n,一定存在等式 n = kp + r ;

  其中k、r是整数,且 0 ≤ r p,称呼k为n除以p的商,r为n除以p的余数。

  分析:为了证明xed≡x(mod n),只要证明φ(n)是xed-x的因数即可。又因为n=pq,而p,q都是素数,故只要证明p和q都是xed-x的因数即可[微软中国6] ,即

  (4) 计算 d 满足 d*e≡1 (mod φ(n)) (保密); (d为e的逆元,可通过扩展的欧几里得算法进行求解)

  (5) {e,n}为公钥,{d,n}为私钥,也可以用{e,d}表示密钥对

  分析:解xed≡x(mod n)同余式方程,该方程可能有n个解[微软中国8] ,这n个解都在模n的同一个剩余类中,小于n的解只有一个,由于明文小于n[微软中国9] ,则该解即是明文x。而xedmod n得到的就是小于n的那个解。

  另外,注意密文c并不等于xe而是c≡xe(mod n)。这里有上一段中我们知道要想求出明文x,解同余式方程xed≡x(mod n)可得,这时只要等式左边的数与X同余就能得到正确的明文。由于c≡xe(mod n),所以可得cd≡xed(mod n),所以cd≡xe(mod n)。

  当B与n不互素时,由于n=p*q,B必然能被p或者q整除,假设B=k*p[微软中国11] ,则B与q互素。再运用费马定理有:

  公钥体制中,单向函数的构造基于大整数n因数分解的困难 ,因而n的两个因数p与q都应取大素数。为便于理解,我们选取两个较小的素数来说明该体制的实施。

  (3)用户A将明文x=3 加密并签名后发给B,B解密并验证签名试把加密通信过程详细写出。

  随机选取与φ(n)=192互素的两个数e1=7和e2=13,并建立同余方程

  将密钥{7,55}和{13.133}交给A和B两个人。将n,e1,e2公开,d1,d2交给A和B各自秘密保管。φ(n)=192由密钥制作者保管。

  B得到密文后,先查到A的公钥7,用7解密密文z=211,得到y。在使用自己的私钥对y进行验证得到信息x=3。[微软中国13]

  是,因为素数不能再分了。即使已知一个大数能分成俩个素数的乘积(已知因数个数)其分解仍然很难吗?

  [微软中国3]同余方程中若a与n互素则方程必有且只有一个解,这也是RSA加解密函数中使用的。

  [微软中国5]为什么e要与φ(n)互素?因为只有e和φ(n)互素了,同余方程ed≡1(mod φ(n))才有且仅有一个解。

  [微软中国6]两个数的最小公倍数=p*q/两个数的最大公约数,若两个数互素(不一定非得全是素数)则两数最大公约数为1,即互素的两个数的最小公倍数就是这两个数的积。而两个数的公倍数都是其最小公倍数的倍数。所以n=pq是p和q的最小公倍数,而只要证明xed-x是p和q的公倍数(即q和p都是xed-x的因数)就可以证明n是xed-x的因数。

  [微软中国8]为什么必有解?因为a是b的倍数?因为未知数本身就是模n的剩余类,而模n的剩余类肯定是存在的。

  1.什么是RSARSA算法是现今使用最广泛的公钥密码算法,也是号称地球上最安全的加密算法。在了解RSA算法之前,先熟悉下几个术语根据密钥的使用方法,可以将密码分为对称密码和公钥密码对称密码:加密和解密...博文来自:dbs1215的专栏

  RSA公钥加密算法是1977年由RonRivest、AdiShamirh和LenAdleman在(美国麻省理工学院)开发的。RSA取名来自开发他们三者的名字。RSA是目前最有影响力的公钥加密算法,它能...博文来自:都是浮云

  Wiki-RSA加密演算法Wiki-欧拉函数Wiki-模反元素ASN.1格式标准RSA算法原理(二)注意:RSA加密或签名后的结果是不可读的二进制,使用时经常会转为BASE64码再传输。RSA加密时,...博文来自:kikajack的博客

  1.RSA算法简介RSA加密算法是一种非对称加密算法。在公开密钥加密和电子商业中RSA被广泛使用。RSA是1977年由罗纳德·李维斯特(RonRivest)、阿迪·萨莫尔(AdiShamir)和伦纳德...博文来自:tanomy的博客

  什么是数字签名?简单来说,签名主要包含两个过程:摘要和非对称加密,首先对需要签名的数据做摘要(类似于常见的MD5)后得到摘要结果,然后通过签名者的私钥对摘要结果进行非对称加密即可得到签名结果。由于计算...博文来自:weixin_40904124的博客

  RSA是在Diffe-Hellman算法问世两年之后,由Rivest、Shamir和Adelman在MIT研究出的,并于1978年公布。RSA系统利用这样的事实:模运算中冥的自乘数是容易解的。RSA的...博文来自:Reoger的博客

  我们可以先思考一个这样的问题,为什么我们把钱可以放心的存放在银行里,或者支付宝里,原因无非就是安全。银行和阿里的安全机制相对来说比较完善 说到加密,目前比较常见的有对称加密和非对称加密,那什么是对称...博文来自:狱蝶阿一的博客

  概述本文旨在说明RSA加密算法的原理及实现,而其相关的数学部分的证明则不是本文内容。版权说明著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。作者:Q-WHai发表日期:2016年2...博文来自:FKNIGHT 的博客

  1、同余(合同式)转载请注明如有疑问欢迎留言两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余记作例如1≡13(mod12)...博文来自:boksic的专栏

  网上都说简单,但是我觉得这个过程事实上还是挺复杂的,这个论述不陈述原因,只陈述过程。首先明确我们的根本目的:我们是要加密一个信息,再解密一个信息。加密这个信息的方法找到两个质数p和q,把他们俩乘起来得...博文来自:小水的博客

  有兴趣朋友也可以进一步关注公众号“架构之道与术”,获取原文。或扫描如下二维码:2014年2月25日,日本时间上午11点,MT.GOX交易所(俗语门头沟)停盘。众所周知,MT.GOX曾经是比特币最大的交...博文来自:软件开发与架构领域 -体系化知识分享

  RSA的应用RSA是一种非对称加密算法。现在,很多登陆表单的密码的都采用RSA加密,例如京东中的登陆使用公钥对密码进行加密。Base64编码ons-codex包提供了许多编码格式...博文来自:qy20115549的博客

  RSA算法数学原理(简单版)原文:[RSA算法数学原理(摘录)][1]本人对原文有误的地方小修改。RSA加密算法是最常用的非对称加密算法,CFCA在证书服务中离不了它。但是有不少新来的同事对它不太了解...博文来自:sitebus的博客

  RSA算法它是第一个既能用于数据加密也能用于数字签名的算法。它易于理解和操作,也很流行。算法的名字以发明者的名字命名:RonRivest,AdiShamir和LeonardAdleman。但RSA的安...博文来自:ghevinn欢迎您光临

  Hash,一般翻译做“散列”,也有直接音译为“哈希”的,就是把任意长度的输入(又叫做预映射,pre-image),通过散列算法,变换成固定长度的输出,该输出就是散列值。这种转换是一种压缩映射,也就是...博文来自:Beyond_2016的博客

  首先说下需求:用OpenSSL 生成了公钥和私钥文件,格式为PEM的,现在用C#想要从文件中读取公钥和私钥 我已经研究了大半天了,网上搜了很久,包括很多英文网站,还是没有头绪 因为不是单独的网站需要用论坛

  本文介绍RSA2加密与解密,RSA2是RSA的加强版本,在密钥长度上采用2048,RSA2比RSA更安全,更可靠,本人的另一篇文章RSA已经发表,有想了解的可以点开下面的RSA文章,但RSA2在明文的...博文来自:chesterccw的博客

  25行代码实现完整的RSA算法  网络上很多关于RSA算法的原理介绍,但是翻来翻去就是没有一个靠谱的算法实现,即使有代码介绍,也都是直接调用JDK或者Python代码包中的API实现,或者即使有代码也...博文来自:专栏

  加密技术加密技术是对信息进行编码和解码的技术,编码是把原来可读信息(又称明文)译成代码形式(又称密文),其逆过程就是解码(解密),加密技术的要点是加密算法,加密算法可以分为三类:1.对称加密2.非对称...博文来自:总结沉淀

  RSA是目前最有影响力和最常用的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被ISO推荐为公钥数据加密标准。RSA算法基于一个十分简单的数论事实:将两个大质数相乘十分容易,但是想要对其...博文来自:zcjcsl的博客

  前言总括:本文详细讲述了RSA算法详解,包括内部使用数学原理以及产生的过程。原文博客地址:RSA算法详解知乎专栏&&简书专题:前端进击者(知乎)&&前端进击者(简书)博主博客地址:Damonare的个...博文来自:前端小渣

  图为RSA公开密钥算法的发明人,从左到右RonRivest,AdiShamir,LeonardAdleman.照片摄于1978年RSA加密算法是最常用的非对称加密算法,CFCA在证书服务中离不了它...博文来自:的博客

  一切操作都在本机执行,不需要进入远程主机/服务器~~1.生成密钥。默认生成的是rsa加密。ssh-keygen2、私钥是给本地的,公钥是给远程的。下面将公钥上传到远程服务器~ssh-copy-idza...博文来自:浮梦一场

  在RSA中,最大值(称为max)由随机挑选的两个素数相乘而得。公钥和密钥在0和最大值之间挑选(称为pub和priv)。为了加密一个数字,让这个数字自己乘自己pub次,并确保当乘积大于最大值时能够回折(...博文来自:墨的博客

  ElGamal公钥密码基于有限域上离散对数问题的公钥密码体制,最著名的是ElGamal体制,是由T.ElGamal在1985年提出的ElGamal有较好的安全性,同一明文在不同时刻会产生不同的密文应用...

  1.图是什么: 图由顶点(vertex,node)和边(edge)组成。顶点就是代表对象,因为有时候题不会直接给顶点,而是某种对象,直接看成顶点即可。我们使用链接两顶点之间的线段来表示。顶点的集合V,...

  一、引言 随着网络技术的飞速发展,信息安全性已成为亟待解决的问题。公钥密码体制中,解密和加密密钥不同,解密和加密可分离,通信双方无须事先交换密钥就可建立起保密通信,较好地解决了传统密码体制在网络通信中...

  定义在数论,特别是整除理论中,原根是一个很重要的概念。对于两个正整数 ,由欧拉定理可知,存在正整数,比如说欧拉函数,即小于等于的正整数中与互素的正整数的个数,使得 。由此,在时,定义对模的指数    ...

  一 用RSA生成签名在RSA中,被签名的消息、密钥以及最终生成的签名都是以数字形式表示的。在对文本进行签名时,需要事先对文本编码成数字。用RSA生成签名的过程可用下列公式来表述:这里所使用的D和N就是...

  最近很多人问,如何将内网的摄像机流媒体数据发布到公网,如果用公网与局域网间的端口映射方式太过麻烦,一个摄像机要做一组映射,而且不是每一个局域网都是有固定ip地址,即使外网主机配置好了每一个摄像机的映射...

  一、图像内插-最近邻内插法 1、数学原理      当一幅二维数字图像从源图像N*M被放为(j*N) * (k*M)目标图像是,参照数学斜率计算公式      必然有: (X1 – Xmin)/...

  帐号相关流程注册范围 企业 政府 媒体 其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...

  专注于cocos+unity+服务器全栈倾斜摄影模型生成DSM、DOM操作流程

  LCD RGB 控制技术讲解 — 时钟篇(上)个人笔记,欢迎转载,请注明出处,共同分享 共同进步

  人有三样东西是无法隐瞒的,咳嗽,穷困和爱,你想隐瞒越欲盖弥彰Mybatis中Collection集合标签的使用

  mybatis简单的CURD就不用多说了,网上相关博客文档一大堆。分析一下Mybatis里面的collection聚集查询。 假设一个班级有多名学生为例,通过班级号查询出该班级的信息,和班级里面的所...

  minpann的博客Unity-Loom的多线.Loom的原理Loom继承自MonoBehaviour,在Unity流程管理中Update方法下检查需要回调的Action进行加锁并回调,确保在主线程执行,回调序列本身又作为静态数据保存,在任意线...

  09-25阅读数 9万+Java中的ThreadLocal类允许我们创建只能被同一个线程读写的变量。因此,如果一段代码含有一个ThreadLocal变量的引用,即使两个线程同时执行这段代码,它们也无法访问到对方的Thread...

  05-08阅读数 19万+小疯手把手带你整合SpringMVC+Spring+MyBatis三大框架,俗称SSM,用它完全代替传统的SSH框架,把它们最优雅的一面发挥出来。整合配置结束后,会有一个应用实例“图书管理系统”带给大...

  04-07阅读数 1万+1、错误:                 键盘遮挡输入框最常见的可能就是在登录界面了,无论有多少个textFiled,不论是在VC的任何位置。都有可能造成键盘弹出来时,把输入框挡住了。...

  06-29阅读数 28万+最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...

  11-16阅读数 66万+强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...

  11-25阅读数 54万+jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...

  阅读数 9万+最近在论坛中看到了很多实用html5开发视频播放,音乐播放的功能,大部分都在寻找答案。因此我就在这里做一个demo,供大家相互学习。html5开发越来越流行了,而对于视频这一块也是必不可少的一部分。如...

http://homeschoolwwh.com/suanfabaomi/407.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有