2014 ISCC 赛题总结之密码学

admin

2014 ISCC 赛题总结之密码学

一．Basic

经之五事索其情

Category:孙子教学→10 Passed/Submitted: 231/4035 Score: 50

孙子曰：“故经之以五事，校之以计而索其情：一曰道，二曰天，三曰地，四曰将，五曰法。”

你是否熟悉RSA算法？敌军正在用RSA算法加密，但是防范不周，被我军获取了部分信息。请解密密文是981，w = 13，n = 2537，分解式的一个因子是43的明文。

flag:  704

RSA算法：

加密原理：用RSA加密信息首先要生成密匙，随机选取两个不相等的质数p，q；两者相乘n=p*q，解出n；计算欧拉函数φ(n)=(p-1)*(q-1)；随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质；计算模反元素d，de=1mod(φ(n)),即de-1=k(φ(n)),k为整数。

至此RSA加密所需要的全部元素以列出，包括p,q,n,φ(n),e,d.其中(n,e)构成公匙，(n,d)构成密匙。(n,e)对外公布，通讯双方加密信息使用；其他四个全部保密，(n,d)解密使用。

加密过程：例如要对明文m加密，需要用公匙(n,e)，只需计算m^e=c mod(n),即密文c为m的e次幂除以n所得的余数。

解密过程：解密过程即是求m，需要用私匙(n,d)，解出等式c^d=m mod(n),得出m即是明文。正常的信息加密过程中d是被严格保密的，所以破解d就是破解密文的关键。因为只有(n,e)是公开的，根据de=1mod(φ(n)),要想知道d，必须知道φ(n)，因为φ(n)=(p-1)*(q-1)，要想知道φ(n)必须知道p,q；因为n=p*q；所以要想知道p,q必须因式分解n，但若n很大，分解n几乎是不可能的，所以就达到了加密的效果。

题目解析：本题中已知密文981，w = 13，n = 2537，以及一个因子43。对应算法中的变量即是m=981,n=2537,e=13,p=43。其中q=n/p=59,φ(n)=2436,所以只剩一个d没有解出。因为de=1 mod(φ(n))即de-kφ(n)=1,所以可根据欧几里得算法

1. 13d-2636k=1
   
2. 13d-5k=1
   
3. 3d-5k=1
   
4. 3d-2k=1
   
5. d=1

复制代码

从上向下分析，从下向上反推得出最终的d

1. =>>>>>>d=937

复制代码

然后算c的d次幂对n取余即得明文m=704.

二．知己知彼

Category:孙子教学→2 Passed/Submitted: 410/17108 Score: 50

知彼知己者，百战不殆；不知彼而知己，一胜一负；不知彼不知己，每战必殆。孙子手下将士截获了敌军命令密文4545 424545 454542 454542 42 424542 424545，你能解密成明文，做到知己知彼吗？

Flag：ISCCAM

摩斯密码：通过‘*’和‘-’不同的排列顺序来表达不同的英文字母、数字和标点符号。‘*’的ASC码值为42，‘-’的ASC码值为45.

凯撒密码：通过字母的简单位移进行信息加密。

题目解析：题目给出了42和45交替出现的一串字符，当数字在33到127之间时联想ASC码值，此时上述的4545 424545 454542 454542 42 424542 424545可转化为：

1. --   -->  M
   
2. *--  -->  W
   
3. --*  -->  G
   
4. --*  -->  G
   
5. *    -->  E
   
6. *-*  -->  R
   
7. *--  -->  W

复制代码

数字转化为左侧的*和-其本身有可转化为对应的字母MWGGERW此时提交并不正确，在根据凯撒位移与本次比赛的主题“ISCC”，将MWGGERW向左移动4为可得：ISCCANS。

三．虚实密文

Category:孙子教学→8 Passed/Submitted: 215/19491 Score: 50

孙子曰：“故策之而知得失之计，作之而知动静之理，行之而知死生之地，角之而知有余不足之处。”

截获敌军情报是掌握敌军动向的一个好方法，也许这种加密方法可能不多见，但是只要能看破密文中的虚虚实实的消息，就能拿到我们所希望的信息。

FLAG：freedom

培根密码：利用A，B的组合加密文字信息，五个一组，有时候加密是隐式的，加密者需使用两种不同字体。即两种字体分别代表A型和B型。然后假信息中的每个字母按字体来决定其代表“A”还是“B”。上述图片中字母分为五个一组，即

1. FEARC ANHOL DUPRI SONER HOPEC ANSET UFREE
   
2. AABAA BAAAA AABAA AABAA AAABB ABBAB ABABB
   
3. f     r     e     e     d     o     m

复制代码

四．密码学补充

1.字母频率猜解：所有的单字母替换的加密的方法都可以用字母频度解决，因为英文中字母出现的频率是一定的，在对大面积的单词统计后发现：

E是使用频率最高的，下面是英文字母使用频率表%)

1. A 8.19 B 1.47 C 3.83 D 3.91 E 12.25 F 2.26 G 1.71
   
2. H 4.57 I 7.10 J 0.14 K 0.41 L 3.77 M 3.34 N 7.06
   
3. O 7.26 P 2.89 Q 0.09 R 6.85 S 6.36 T 9.41
   
4. U 2.58 V 1.09 W 1.59 X 0.21 Y 1.58 Z 0.08

复制代码

当破解一个较长的密文时可以统计处其中字母出现的频率，然后根据频率表做相应的替换，就可推断出明文。

2.阑珊密码：阑珊密码即是把明文分成N组，分别把每组的第一个，第二个。。。。。连接起来，再拼凑成一个字符串。例如对明文 I AM A STUDENT 加密。

两个一组可以得到IA MA ST UD EN T，抽取第一个字母可以得到IMSUET，第二个字母可得到AATDN，连在一起就是IMSUETAATDN。

破解时将密文从中间分开IMSUET和AATDN，再按上下顺序组合起来，可得I AM A STUDENT。

3.维吉尼亚密码：为了对抗字母频度猜解，在凯撒密码的基础上发展出一种多表替换的密码。维吉尼亚密码引出密匙概念，根据密匙来决定用哪一行密表来进行加密。

常规密表如下：

1. A -B C D E F G H I J K L M N O P Q R S T U V W X Y Z
   
2. A -A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
   
3. B -B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
   
4. C -C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
   
5. D -D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
   
6. E -E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
   
7. F -F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
   
8. G -G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
   
9. H -H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
   
10. I -I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
    
11. J -J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
    
12. K -K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
    
13. L -L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
    
14. M -M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
    
15. N -N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
    
16. O -O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
    
17. P -P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
    
18. Q -Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
    
19. R -R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
    
20. S -S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
    
21. T -T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
    
22. U -U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
    
23. V -V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
    
24. W -W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
    
25. X -X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
    
26. Y -Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
    
27. Z -Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

复制代码

对如下明文加密：

1. TO BE OR NOT TO BE THAT IS THE QUESTION

复制代码

当选定RELATIONS作为密钥时，加密过程是：明文一个字母为T，第一个密钥字母为R，因此可以找到在R行中代替T的为K，依此类推，得出对应关系如下：

1. 密钥:RELAT IONSR ELATI ONSRE LATIO NSREL
   
2. 明文:TOBEO RNOTT OBETH ATIST HEQUE STION
   
3. 密文:KSMEH ZBBLK SMEMP OGAJX SEJCS FLZSY

复制代码

来源：网络转载