2014 ISCC 赛题总结之密码学

2014-08-13 +7 544886人围观 ,发现 16 个不明物体 其他

一.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,所以可根据欧几里得算法

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

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

=>>>>>>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可转化为:

--   -->  M
*--  -->  W
--*  -->  G
--*  -->  G
*    -->  E
*-*  -->  R
*--  -->  W

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

三.虚实密文

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

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

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

FLAG:freedom

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

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

四.密码学补充

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

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

A 8.19 B 1.47 C 3.83 D 3.91 E 12.25 F 2.26 G 1.71
H 4.57 I 7.10 J 0.14 K 0.41 L 3.77 M 3.34 N 7.06
O 7.26 P 2.89 Q 0.09 R 6.85 S 6.36 T 9.41
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.维吉尼亚密码:为了对抗字母频度猜解,在凯撒密码的基础上发展出一种多表替换的密码。维吉尼亚密码引出密匙概念,根据密匙来决定用哪一行密表来进行加密。

常规密表如下:

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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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

对如下明文加密:

TO BE OR NOT TO BE THAT IS THE QUESTION

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

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

ps:第一次写文章,如有不当还请指正,谢谢!

相关推荐

这些评论亮了

  • 艾斯比 回复
    说句实话:现在研究这种老式密码还做成谜题的都是有病,现实中根本不可能用到这些,强度低易碰撞,不符合加密原则。做这种题跟打DOTA没有本质的区别,都是娱乐,不能提升自己的CTF纯属浪费时间。
    同样是密码学的东西,跟:2014年澳大利亚信息安全挑战 CySCA CTF 官方write up Crypto篇 这篇文章比,高下立分。
    )20( 亮了
发表评论

已有 16 条评论

取消
Loading...
X-man

这家伙太懒,还未填写个人描述!

1 文章数 4 评论数 0 关注者

特别推荐

推荐关注

活动预告

填写个人信息

姓名
电话
邮箱
公司
行业
职位
css.php