马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。
您需要 登录 才可以下载或查看,没有账号?立即注册
x
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,所以可根据欧几里得算法 - 13d-2636k=1
- 13d-5k=1
- 3d-5k=1
- 3d-2k=1
- d=1
复制代码 从上向下分析,从下向上反推得出最终的d
然后算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
复制代码
来源:网络转载
|