分类目录归档:CS

RSA算法原理【轉】

【原文鏈接】

https://www.cnblogs.com/gwind/p/8013116.html

【原文摘錄】

一、基础数论

1、互质关系

  • 如果两个正整数,除了1以外,没有其他公因子,我们就称这两个数是互质关系(coprime)。比如,15和32没有公因子,所以它们是互质关系。这说明,不是质数也可以构成互质关系。

2、欧拉函数

  • 定义:任意给定正整数n,请问在小于等于n的正整数之中,有多少个与n构成互质关系?(比如,在1到8之中,有多少个数与8构成互质关系?),计算这个值的方法就叫做欧拉函数,以φ(n)表示。
  • 欧拉函数求法及性质:
    1. 对于素数p, φ(p)=p-1,对于对两个素数p,q, φ(pq)=pq-1,欧拉函数是积性函数,但不是完全积性函数.
    2. 对于一个正整数N的素数幂分解N=P1^q1*P2^q2*…*Pn^qn,则φ(N)=N*(1-1/P1)*(1-1/P2)*…*(1-1/Pn).
    3. 除了N=2,φ(N)都是偶数.
    4. 如果n可以分解成两个互质的整数之积,n = p1 × p2,则φ(n) = φ(p1p2) = φ(p1)φ(p2)

二、RSA加密

第一步,随机选择两个不相等的质数p和q。

爱丽丝选择了61和53。(实际应用中,这两个质数越大,就越难破解。)

第二步,计算p和q的乘积n。

爱丽丝就把61和53相乘。

  n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001,一共有12位,所以这个密钥就是12位。实际应用中,RSA密钥一般是1024位,重要场合则为2048位。

第三步,计算n的欧拉函数φ(n)。

根据公式:

  φ(n) = (p-1)(q-1)

爱丽丝算出φ(3233)等于60×52,即3120。

第四步,随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。

爱丽丝就在1到3120之间,随机选择了17。(实际应用中,常常选择65537。)

第五步,计算e对于φ(n)的模反元素d。

所谓“模反元素”就是指有一个整数d,可以使得ed被φ(n)除的余数为1。

  ed ≡ 1 (mod φ(n))

这个式子等价于

  ed – 1 = kφ(n)

于是,找到模反元素d,实质上就是对下面这个二元一次方程求解。

  ex + φ(n)y = 1

已知 e=17, φ(n)=3120,

  17x + 3120y = 1

这个方程可以用“扩展欧几里得算法”求解,此处省略具体过程。总之,爱丽丝算出一组整数解为 (x,y)=(2753,-15),即 d=2753。

至此所有计算完成。

第六步,将n和e封装成公钥,n和d封装成私钥。

在爱丽丝的例子中,n=3233,e=17,d=2753,所以公钥就是 (3233,17),私钥就是(3233, 2753)。

实际应用中,公钥和私钥的数据都采用ASN.1格式表达(实例)。

七、RSA算法的可靠性

回顾上面的密钥生成步骤,一共出现六个数字:

  p
q
n
φ(n)
e
d

这六个数字之中,公钥用到了两个(n和e),其余四个数字都是不公开的。其中最关键的是d,因为n和d组成了私钥,一旦d泄漏,就等于私钥泄漏。

那么,有无可能在已知n和e的情况下,推导出d?

  (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。

(2)φ(n)=(p-1)(q-1)。只有知道p和q,才能算出φ(n)。

(3)n=pq。只有将n因数分解,才能算出p和q。

结论:如果n可以被因数分解,d就可以算出,也就意味着私钥被破解。

可是,大整数的因数分解,是一件非常困难的事情。目前,除了暴力破解,还没有发现别的有效方法。维基百科这样写道:

  ”对极大整数做因数分解的难度决定了RSA算法的可靠性。换言之,对一极大整数做因数分解愈困难,RSA算法愈可靠。

假如有人找到一种快速因数分解的算法,那么RSA的可靠性就会极度下降。但找到这样的算法的可能性是非常小的。今天只有短的RSA密钥才可能被暴力破解。到2008年为止,世界上还没有任何可靠的攻击RSA算法的方式。

只要密钥长度足够长,用RSA加密的信息实际上是不能被解破的。”

举例来说,你可以对3233进行因数分解(61×53),但是你没法对下面这个整数进行因数分解。

  12301866845301177551304949
58384962720772853569595334
79219732245215172640050726
36575187452021997864693899
56474942774063845925192557
32630345373154826850791702
61221429134616704292143116
02221240479274737794080665
351419597459856902143413

它等于这样两个质数的乘积:

  33478071698956898786044169
84821269081770479498371376
85689124313889828837938780
02287614711652531743087737
814467999489
×
36746043666799590428244633
79962795263227915816434308
76426760322838157396665112
79233373417143396810270092
798736308917

事实上,这大概是人类已经分解的最大整数(232个十进制位,768个二进制位)。比它更大的因数分解,还没有被报道过,因此目前被破解的最长RSA密钥就是768位。

八、加密和解密

有了公钥和密钥,就能进行加密和解密了。

(1)加密要用公钥 (n,e)

假设鲍勃要向爱丽丝发送加密信息m,他就要用爱丽丝的公钥 (n,e) 对m进行加密。这里需要注意,m必须是整数(字符串可以取ascii值或unicode值),且m必须小于n。

所谓”加密”,就是算出下式的c:

  me ≡ c (mod n)

爱丽丝的公钥是 (3233, 17),鲍勃的m假设是65,那么可以算出下面的等式:

  6517 ≡ 2790 (mod 3233)

于是,c等于2790,鲍勃就把2790发给了爱丽丝。

(2)解密要用私钥(n,d)

爱丽丝拿到鲍勃发来的2790以后,就用自己的私钥(3233, 2753) 进行解密。可以证明,下面的等式一定成立:

  cd ≡ m (mod n)

也就是说,c的d次方除以n的余数为m。现在,c等于2790,私钥是(3233, 2753),那么,爱丽丝算出

  27902753 ≡ 65 (mod 3233)

因此,爱丽丝知道了鲍勃加密前的原文就是65。

至此,”加密–解密”的整个过程全部完成。

我们可以看到,如果不知道d,就没有办法从c求出m。而前面已经说过,要知道d就必须分解n,这是极难做到的,所以RSA算法保证了通信安全。

你可能会问,公钥(n,e) 只能加密小于n的整数m,那么如果要加密大于n的整数,该怎么办?有两种解决方法:一种是把长信息分割成若干段短消息,每段分别加密;另一种是先选择一种”对称性加密算法”(比如DES),用这种算法的密钥加密信息,再用RSA公钥加密DES密钥。

九、私钥解密的证明

最后,我们来证明,为什么用私钥解密,一定可以正确地得到m。也就是证明下面这个式子:

  cd ≡ m (mod n)

因为,根据加密规则

  me ≡ c (mod n)

于是,c可以写成下面的形式:

  c = me – kn

将c代入要我们要证明的那个解密规则:

  (me – kn)d ≡ m (mod n)

它等同于求证

  med ≡ m (mod n)

由于

  ed ≡ 1 (mod φ(n))

所以

  ed = hφ(n)+1

将ed代入:

  mhφ(n)+1 ≡ m (mod n)

接下来,分成两种情况证明上面这个式子。

(1)m与n互质。

根据欧拉定理,此时

  mφ(n) ≡ 1 (mod n)

得到

  (mφ(n))h × m ≡ m (mod n)

原式得到证明。

(2)m与n不是互质关系。

此时,由于n等于质数p和q的乘积,所以m必然等于kp或kq。

以 m = kp为例,考虑到这时k与q必然互质,则根据欧拉定理,下面的式子成立:

  (kp)q-1 ≡ 1 (mod q)

进一步得到

  [(kp)q-1]h(p-1) × kp ≡ kp (mod q)

  (kp)ed ≡ kp (mod q)

将它改写成下面的等式

  (kp)ed = tq + kp

这时t必然能被p整除,即 t=t’p

  (kp)ed = t’pq + kp

因为 m=kp,n=pq,所以

  med ≡ m (mod n)

原式得到证明。

C语言端序【轉】

【原文鏈接】

http://blog.csdn.net/jixingzhong/article/details/1486110

【原文摘錄】

Endianism,端序,是指用来存储数据的方法,它定义了数据类型对字节进行寻址的方式。

两种端序方式:
1、Little-endian,小端序,是将低位字节存储在内存偏移地址较低的地址中,将高位字节存储在内存偏移地址较高的地址中;
2、Big-endian,大端序,则是将低位字节存储在内存偏移地址较高的地址中,将高位字节存储在内存偏移地址较低的地址中。

比如:
0x12345678 在 big-endian 系统上的布局
内存偏移量     0     1     2     3
内存内容       0x12     0x34     0x56     0x78

0x12345678 在 little-endian 系统上的布局
内存偏移量     0     1     2     3
内存内容     0x78     0x56     0x34     0x12

机器大小端和环境相关,可以使用下面的办法判断机器的大小端:
#include <cstdlib>
#include <iostream>

using namespace std;

union test
{
int i;
char c;
};

int main()
{
union test t;
t.i = 0x12345678;
if(t.c == 0x78)
cout<<“Little-endism”<<endl;
else
cout<<“Big-endism”<<endl;
system(“pause”);
return 0;
}

在获悉环境的大小端后,就可以进行细致的分析了,
比如 Little-endlism 环境下:
#include <cstdlib>
#include <iostream>

using namespace std;

union test
{
int i;
char c;
};

int main()
{
union test t;
t.i = 0x12345678;
short int x= *((short int *)(&(t.c)));
cout<<hex<<x;
system(“pause”);
return 0;
}

0x12345678 在 little-endian 系统上的布局
内存偏移量     0     1     2     3
内存内容     0x78     0x56     0x34     0x12

short int 为2字节(32位平台下)
将访问:
内存偏移量     0     1
内存内容     0x78     0x56
所以, 最后的结果为 (0x)5678

Endianism 在以下情况中非常重要:
1.使用位掩码时
2.对象的间接指针地址部分

合理使用联合体、位域等手段,可以在一定程度避免端序问题。

对称加密和分组加密中的四种模式(ECB、CBC、CFB、OFB)【轉】

【原文鏈接】

http://www.cnblogs.com/happyhippy/archive/2006/12/23/601353.html

【原文內容】

. AES对称加密:


AES加密

分组

. 分组密码的填充

分组密码的填充

e.g.:

PKCS#5填充方式

. 流密码:

. 分组密码加密中的四种模式:

3.1 ECB模式

优点:

1.简单;

2.有利于并行计算;

3.误差不会被传送;

缺点:

1.不能隐藏明文的模式;

2.可能对明文进行主动攻击;


3.2 CBC
模式:

优点:

1.不容易主动攻击,安全性好于ECB,适合传输长度长的报文,是SSL、IPSec的标准。

缺点:

1.不利于并行计算;

2.误差传递;

3.需要初始化向量IV

 

3.3 CFB模式:

优点:

1.隐藏了明文模式;

2.分组密码转化为流模式;

3.可以及时加密传送小于分组的数据;

缺点:

1.不利于并行计算;

2.误差传送:一个明文单元损坏影响多个单元;

3.唯一的IV;

 

3.4 OFB模式:

优点:

1.隐藏了明文模式;

2.分组密码转化为流模式;

3.可以及时加密传送小于分组的数据;

缺点:

1.不利于并行计算;

2.对明文的主动攻击是可能的;

3.误差传送:一个明文单元损坏影响多个单元;

happyhippy作者:Silent Void
出处:http://happyhippy.cnblogs.com/
转载须保留此声明,并注明在文章起始位置给出原文链接。

国际顶尖高校的CS核心课——MIT【轉】

摘自:
http://user.qzone.qq.com/24035234/blog/1486603772
原文:
国际顶尖高校的CS核心课——MIT
MIT的相关院系名称是EECS,其专业方向有四个,分别是EE,EECS,CS,CS(BIO)。
吐一下CAO的话,国内很多高校这些东西都是在三、四个院开设的,所以就不多谈了吧。
这里谈CS,所以我们更关心的是第三个方向,下面就只讲这个吧。
先上图来看看!

psb
很明显这个必修的核心课和UCB相比,多了很多,有十门之多(多选一的课程仅计一门),除开离散数学(6.042)也有九门。
以下简单看一下各门课代号所对应的国内课程名称(事实上,在内容上不完全与国内课程等价)。
从上往下看分别是:

Header(专业课):

6.031: 软件构造基础(软件工程?) 6.033 计算机系统工程 6.034 AI,6.036 ML   6.045 理论   6.046 算法设计与分析
Foundation(专业基础课):

6.004 计算机结构   6.009 编程基础(数据结构+算法+PYTHON+SE) 6.006 算法

计算机数学:6.042 离散

编程技能:6.0001 : PYTHON与计算机科学导论

导论: 6.01机器人感知、软件、控制 6.02网络通信 6.03生物 6.S08 互联的嵌入式系统

几点感想:
其一是这个总体结构和学校给出的总的要求在结构上非常相似啊
其二是其设置了导论课程。此处值得借鉴的地方在于,导论课是相对比较深入的专业导论,而不是完全吹水的哪一种。对于刚进校的新生(此处要特别强调中国高校的新生,因为专心高考绝大多数同学对专业几乎完全没有认知,或者是一些错误的认知),基本听不出个所以然来。MIT的导论课虽然在层级上是位于最下层,但在先后序上,则是在上完编程技能课之后才上的,此时,学生对专业有了一些基本的认知,这样导论课就不再虚,而是落到了实处。后面抽时间,进一步可以看看这些课的内容,搞清楚其到底是如何做的,应该对我们的教学改革有些帮助。另外,从其导论课的开设来看,应该是体现了不同的主题和方向,分了四个导论课选一,而不是广而泛之的导论课,这个更多的是为了满足学生(对专业方向深入理解)的需求。

想强调的是,MIT的课程没有深入跟进,很多课程细节还需要深入了解(后面有空再补充吧)。

最后想说的是这是MIT最新版(2016)的内容,可看其官网:http://student.mit.edu/catalog/m6a.html
国内之前也有总结,不过是上一版的计划。二者还是有些区别的。
另外,图中没有解释的也补充一下吧,UAR好象是毕业论文(R:Research),UAT应该是设计。

国际顶尖高校的CS核心课——UCB【轉】

摘自:http://user.qzone.qq.com/24035234/blog/1486600272
原文:
国际顶尖高校的CS核心课——UCB
先还是上一个最熟悉的高校:UCB,熟悉主要是当年以及现在从其学到很多东西。

UCB的计算机专业,学生应该算是有非常大的选择余地,除了三门核心课程是必需要选的,其他都是可选的(当然,也可以不选)。好吧,是不是太自由了点。
嗯,还是快速切入主题吧。
三门核心课:61A,61B,61C
61A:源于MIT的经典课和书籍SICP,事实上这本书被搞ACM比赛的师生奉为圣经,对于大多数学CS的同学来说,怕是读到了研究生,仍然觉得读起来异常困难。好吧,事实是UCB给大一的同学讲这门课。从头看过这门课的视频,窃以为,UCB的老师非常成功的浓缩了原书的精华,以极其小白的方式(容易理解的方式)进行了认真的诠释,配以作业,最后完成了一门语言的解释器(现如今有很多流行的语言都是解释型的,如PYTHON,PERL,JS,甚至有C语言的解释型版本CH)。
很长一段时间,UCB用的都是原书所用的SCHEME语言(LISP变种)来讲授这门课,近几年,也随大流,转而用PYTHON来讲了。但在内容上还是和原来的一样。(MIT则是从内容到所用语言都做了很大的改革)

61B:主要是讲数据结构的内容,这个基本上所有学校都有的,好象也就没有什么特色可言。

61C:主要是讲计算机的原理,可以认为把整个计算机过了一遍,软硬通吃。
在软件方面,从C到汇编再到机器语言最后是程序的启动。基本是走通了MS的VS所做的事情。特色讲汇编不是要理解指令,而是把高级语言翻译过来,讲机器语言,更看重机器语言的设计及准则,这些设计与准则当然不是空洞的教条,而是用鲜活的例子来呈现。
在硬件方面,则从开关电路开始,一步步进行集成,最后构建出物理计算机来执行指令集,从而彻底打通任督二脉。
在单机性能方面,主要是讲如何突破物理限制瓶颈,流水线,CACHE,VM等。而有了思路之后,更重要的是如何克服一些困难,从而最终解决这些问题,体现前世工程师的智慧。
最近更是加进去了云计算HADOOP的一些内容。
当然硬件方面还有一些内容,IO与磁盘等,这里也是讲一些有意思的核心内容,轮询与中断,RAID等。