一道有意思的相亲题目-蓝桥杯
知乎上的提问
听说解出这道题目就能加群找真爱，哈哈哈哈
反正我是被吓到了
然后我好奇进去了
题目
听说要翻墙才能进整鱼两吃 ，不过这对于技术宅应该都是小问题
上面是题目原型，我勒个去牙膏脸，神马鬼啊，我一看到反正是被吓傻了，莫慌，咱们找找规律
先探探这个是啥语言
begin开头 每段开头为M end结尾
google一下
原来是UUENCODE，我勒个去
这个时候我们需要万能的Google，解码UUENCODE
切记不要使用百度，使用百度搜索的结果会让你大开眼界题目的第一个问题
# Welcome## KeyRSA Public Key: (N, 7)N = 233 * MM is the greatest four-digit prime that makes N end with 233## Encrypted Audit QQ group numberThe Audit QQ group number is encrypted with the **RSA Public Key**.
第一步解出M
翻译：M是使尾数为233的N的最大四位数
然后我写了一个脚本
node.js版
for(var i=999;i<10000;i++){var n=233*i;if(n%1000===233){console.log(i);}}
php版
for($i=999;$i<10000;$i++){$n=233*$i;if ($n%1000==233) {var_dump($i);}}
得出M是9001，倪宝铎N是2097233
第二个问题解出RSA
RSA算法是仨老外提出的，以难以破解著称
这个算法有几个重点
欧拉数
公钥
私钥
加密
解密
首先，给出两个素数，相乘得到n 各自减1得到欧拉数 给出公钥 公钥+欧拉数->私钥
加密:需要给出需要加密的明文+公钥+n 解密:需要给出需要解密的密文+私钥+n
OK想念的歌，然后从题目我们可以知道 两个素数：233，9001 需要解密的密文：197372，333079 公钥：7
这里就比较抓狂了，我们需要写好的RSA算法实现
我先是采用自己编写的RSA算法实现
C语言版
原版，可交互模式
//// Created by 4399-4928 on 2016/7/29.//#include <stdio.h>int candp(int a,int b,int c){ int r=1; b=b+1; while(b!=1){ r=r*a; r=r%c; b--; } printf("%d
",r); return r;}int func(int x,int y){ int t; while (y){ t=x; x=y; y=t%y; } if(x==1) return 0; else return 1;}void main(){ int p,q,e硅谷亮城 ,d,m,n,t,c,r; printf("请输入两个素数p,q:"); scanf("%d%d",&p,&q); n=p*q; printf("计算得n为%3d
",n); t=(p-1)*(q-1); printf("计算得t为%3d
"红巨人,t); printf("请输入公钥:"); scanf("%d",&e); if(e<1||e>t||fun(e,t)){ print("e不符合要求"); scanf("%d"杨思维,&e); } d=1; while(((e*d)%t)!=1) d++; printf("经计算d为%d
",d); printf("加密请输入 1
"); printf("解密请输入 2
"); scanf("%d",&r); switch (r){ case 1:printf("请输入明文");scanf("%d",&m);c=candp(m王贞治,e,n);printf("密文为%d
",c);break; case 2:printf("请输入密文");scanf("%d",&c);m=candp(c,d数九歌,n);printf("明文为%d
",m);break; }}
因为不是经常做C开发，临时下载了一个CLion来写，然后不会用…..竟然不知道怎么Run起来 然后我就对代码做了修改直接就是可以print信息的
// Created by 4399-4928 on 2016/7/29.//#include <stdio.h>int candp(int a,int b,int c){ int r=1; b=b+1; while(b!=1){ r=r*a; r=r%c; b--; } printf("%d
",r); return r;}int func(int x,int y){ int t; while (y){ t=x; x=y; y=t%y; } if(x==1) return 0; else return 1;}void main(){ int d,n,t,m; d=1; n=233*9001; t=(233-1)*(9001-1); while(((7*d)%t)!=1) d++; printf("经计算d为%d
"位面降临,d); m=candp(333079,d,n); printf("明文为%d
",m);}
跑了一下莫名奇妙的结果
经计算d为1193143-1984460明文为-1984460
google+百度了一下，就懒得修改之前写的了，然后采用了好多现成的RSA实现版本
C语言版
php版
python(1)版
python(2)版
javaScript版
像PHP版本解密用的是PHP自带的拓展库，廖雪峰老师的Python使用的是数组的形式传递，由于python技术有限，只能看懂一部分，难以修改，最后选择了python的第二个版本孙集斌，比较容易理解，然后对其进行修改
import randomdef fastExpMod(b, e, m): result = 1 while e != 0: if (e&1) == 1:# ei = 1, then mulresult = (result * b) % m e >>= 1 # b, b^2, b^4, b^8, ... , b^(2^n) b = (b*b) % m return resultdef extendedGCD(a, b): #a*xi + b*yi = ri if b == 0: return (1, 0, a) #a*x1 + b*y1 = a x1 = 1 y1 = 0 #a*x2 + b*y2 = b x2 = 0 y2 = 1 while b != 0: q = a / b #ri = r(i-2) % r(i-1) r = a % b a = b b = r #xi = x(i-2) - q*x(i-1) x = x1 - q*x2 x1 = x2 x2 = x #yi = y(i-2) - q*y(i-1) y = y1 - q*y2 y1 = y2 y2 = y return(x1, y1, a)def computeD(fn, e): (x, y, r) = extendedGCD(fn, e) #y maybe < 0, so convert itif y < 0: return fn + y return ydef keyGeneration(): p = 233 q = 9001 n = p * q fn = (p-1) * (q-1) e = 7 d = computeD(fn, e) return (n, e, d)def decryption(C, d, n): #RSA M = C^d mod n return fastExpMod(C, d, n)#Unit Testing(n, e诗梓佳, d) = keyGeneration()M1 = decryption(197372, d, n)M2 = decryption(333079, d, n)print "%d%d"%(M1,M2)
然后得出结果了
然后就到了一个验证群，但是验证码又是一个问题题目中的第二个问题
# CAPTCHA Use this gist revision `7d23e6e9994bb6fae874dab35e46fd75b9dd15be` result as CAPTCHA.
看英文的意思就是把gist的log调用出来然后reset回去吧
这一步不难，只要对git稍微有点熟悉的人都会明白
再然后就得到了Roman Hitman
然后加群+验证码，就过了骆力炜 ，进群以后各种狂风暴雨
要你回答什么3问，什么奇奇怪怪的喜好等等，然后我看
到了好多程序猿的自曝照片，把我幼小的心灵吓坏了，
而且不发这些信息就只能待10分钟，天了噜，管理的严肃语气把我吓坏了
然后我就退群了……小插曲
我闲着无聊把Roman Hitman放在github里面搜索，发
现了一个奇怪的开源项目
然后我就进去看了一下源码，发现是这个题目的答案……
由于我的python都是临时装的，pip包管理器莫名其妙遇
到了没有权限的问题，可能是windows下的问题，我暂
时也没办法解决所以我也没跑这个项目，感兴趣的人可
以Run试试后记
这道题目还是很有意思的，涉及到的知识点有
uuencode
RSA算法
Git
任意语言的编程能力