注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

RSA公钥脚本转换及m和p*q非互质可解密的说明  

2015-04-11 20:27:49|  分类: 算法思想 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一、从stackoverflow上一篇文章说起
在这篇文章中,作者简单讨论了集中公钥的存储方式,问题的引入是由于RSA公钥密码的存储结构,对于RSA加密来说,公钥有两部分组成,模数modulus和指数exponent,这两个在RSA中表示起来其实都是正整数,如果直接使用整数表示,可能我们看到的就是一些二进制文件而不是文本文件,文本文件在unix体系中更加受欢迎,所以这里就使用了base64编码,将这两个整数转换为可显示的字符串;再说第一个问题,就是RSA公钥是由两部分组成,这两个部分在表示中如何分开呢,使用逗号分开应该也可以,但是这种表示缺乏一个树形结构,无法表示更多信息,并且这种自定义的格式太过私有,最好能够结合上一种通用一些的表示方法,这个表示方法就是asn1方法ASN.1(Abstract Syntax Notation One),在MSDN上也有一个说明,这种格式是表示语法结构的一种通用格式,并非为RSA私有,反而是RSA只是这种语法结构的一个使用实例。
openssl自带了一个解析这种文件的工具openssl asn1parse,在其说明文档中如此解释各个字段的含义
OUTPUT

       The output will typically contain lines like this:

	 0:d=0	hl=4 l= 681 cons: SEQUENCE

       .....

	 229:d=3  hl=3 l= 141 prim: BIT STRING
	 373:d=2  hl=3 l= 162 cons: cont [ 3 ]
	 376:d=3  hl=3 l= 159 cons: SEQUENCE
	 379:d=4  hl=2 l=  29 cons: SEQUENCE
	 381:d=5  hl=2 l=   3 prim: OBJECT	      :X509v3 Subject Key Identifier
	 386:d=5  hl=2 l=  22 prim: OCTET STRING
	 410:d=4  hl=2 l= 112 cons: SEQUENCE
	 412:d=5  hl=2 l=   3 prim: OBJECT	      :X509v3 Authority Key Identifier
	 417:d=5  hl=2 l= 105 prim: OCTET STRING
	 524:d=4  hl=2 l=  12 cons: SEQUENCE

       .....

       This example is part of a self signed certificate. Each line starts
       with the offset in decimal. d=XX specifies the current depth. The depth
       is increased within the scope of any SET or SEQUENCE. hl=XX gives the
       header length (tag and length octets) of the current type. l=XX gives
       the length of the contents octets.
以开始说的stackoverflow上给出的例子,解析其输出为
tsecer@harry: cat pubkey.key 
-----BEGIN RSA PUBLIC KEY-----
MIGJAoGBANxn+vSe8nIdRSy0gHkGoJQnUIIJ3WfOV7hsSk9An9LRafuZXY
UMB6H5RxtWFm72f7nPKlg2N5kpqk+oEuhPx4IrnXIqnN5vwu4Sbc/w8rjE
3XxcGsgXUams3wgiBJ0r1/lLCd6a61xRGtj4+Vae+Ps3mz/TdGUkDf80dV
ek9b9VAgMBAAE=
-----END RSA PUBLIC KEY-----
tsecer@harry: openssl asn1parse -dump -in pubkey.key 
    0:d=0  hl=3 l= 137 cons: SEQUENCE          
    3:d=1  hl=3 l= 129 prim: INTEGER           :DC67FAF49EF2721D452CB4807906A09427508209DD67CE57B86C4A4F409FD2D169FB995D850C07A1F9471B56166EF67FB9CF2A5836379929AA4FA812E84FC7822B9D722A9CDE6FC2EE126DCFF0F2B8C4DD7C5C1AC81751A9ACDF0822049D2BD7F94B09DE9AEB5C511AD8F8F9569EF8FB379B3FD37465240DFF347557A4F5BF55
  135:d=1  hl=2 l=   3 prim: INTEGER           :010001
tsecer@harry: 
这里的展示结果已经由openssl进行了base64的解码,其中展示了使用的modulus和exponent的两个数值对应的16进制表示形式。
二、转换为xml格式的
<RSAKeyValue>
   <Modulus>ANxn+vSe8nIdRSy0gHkGoJQnUIIJ3WfOV7hsSk9An9LRafuZXYUMB6H5RxtWFm72f7nPKlg2N5kpqk+oEuhPx4IrnXIqnN5vwu4Sbc/w8rjE3XxcGsgXUams3wgiBJ0r1/lLCd6a61xRGtj4+Vae+Ps3mz/TdGUkDf80dVek9b9V</Modulus>
   <Exponent>AQAB</Exponent>
</RSAKeyValue>
由于openssl已经展示除了modulus和exponent的16进制内码格式,我们就可以通过工具将它转换为xml识别的base64编码格式,脚本命令为
tsecer@harry: echo -n DC67FAF49EF2721D452CB4807906A09427508209DD67CE57B86C4A4F409FD2D169FB995D850C07A1F9471B56166EF67FB9CF2A5836379929AA4FA812E84FC7822B9D722A9CDE6FC2EE126DCFF0F2B8C4DD7C5C1AC81751A9ACDF0822049D2BD7F94B09DE9AEB5C511AD8F8F9569EF8FB379B3FD37465240DFF347557A4F5BF55 | sed -r 's/(.{2})/\1\n/g' | awk '{print $1}' | grep -e "^$" -v   | (echo -ne "\x0"; while read hex; do echo -ne "\x$hex" ; done; ) | openssl enc -base64
ANxn+vSe8nIdRSy0gHkGoJQnUIIJ3WfOV7hsSk9An9LRafuZXYUMB6H5RxtWFm72
f7nPKlg2N5kpqk+oEuhPx4IrnXIqnN5vwu4Sbc/w8rjE3XxcGsgXUams3wgiBJ0r
1/lLCd6a61xRGtj4+Vae+Ps3mz/TdGUkDf80dVek9b9V
tsecer@harry: echo -n 010001 | sed -r 's/(.{2})/\1\n/g' | awk '{print $1}' | grep -e "^$" -v   | ( while read hex; do echo -ne "\x$hex" ; done; ) | openssl enc -base64               
AQAB
在第一个表达式的前面加上了echo -ne"\x0"主要是由于前面有一个0的填充,只是为了让结果和作者给出的内容相同,不填充的话整数和填充之后内容相同。
三、RSA中message m和pq不互质的情况
在通常教科书中对于算法的证明都是假设消息m和pq是互质的,在不互质的情况下解密是否成立呢?答案是肯定的,在下面这个位置中有比较简洁的描述。假设m和p非互质,则m=0 mod p,则m^(e*d)=0 =m mod p,也就是说 m^(e*d)-m=0 mod p,这一点对于<m,q>组合同样生效,所以就是说
m^(e*d)-m=0 mod q,
由于 m^(e*d)-m同时被p和q整除,所以它也被q*q整除,
说明无论m是否和p、q互质,加解密的算法均是成立的。
四、简单验证下
选择59、61这两个素数分别作为p和q,则modulus为3599,以23作为exponent,则私钥为
tsecer@harry: for ((i=1; i < 3599; i++)) do if ((i*23%((59-1)*(61-1))==1))  ; then  echo $i ; fi ; done
1967
tsecer@harry: cat rsademo.cpp 
#include <stdio.h>
#define MOD 3599
#define ENC 23
#define DEC 1967
int enc(int val)
{
int iret =1;
for (int i = 0; i < ENC; i++)
{
iret = iret * val % MOD;
}
return iret;
}

int dec(int val)
{
int iret =1;
for (int i = 0; i < DEC; i++)
{
iret = iret * val % MOD;
}
return iret;
}
int main()
{
for (int i = 1; i < MOD; i++)
{
printf("%d dec %d\n", i, dec(enc(i)));
}
}
tsecer@harry: g++ rsademo.cpp 
tsecer@harry: ./a.out | tail 
3589 dec 3589
3590 dec 3590
3591 dec 3591
3592 dec 3592
3593 dec 3593
3594 dec 3594
3595 dec 3595
3596 dec 3596
3597 dec 3597
3598 dec 3598
tsecer@harry: ./a.out | awk -F"dec" '{if ($1 != $2) print}'
tsecer@harry: 
  评论这张
 
阅读(169)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017