教你一个传纸条不被班主任抓住的法子
缘起
有一天，小明和小红在课堂上传纸条又被老师抓了个现行，还被破获了他们俩放学后去打超级玛丽的计划。这让两个小朋友很是懊悔，遂一起商量着要发明一套密语。就算被班主任抓住了，也没办法破译纸条里面的内容。
约定
聪明的小明很快就想出了一个酷炫的加密方式，遂找上小红，开始介绍他的方案。
小明拿出纸和笔，耐心地跟小红讲解起来了：“首先，我们需要两个质数，为了计算方便，我们选择$13$和$17$。”
小红很快反应过来：“对，我在读四年级的时候，数学老师有教过，质数就是除了$1$和本身之外没有其他因数的整数。”
“真是个小聪明！”小明很是欣慰，“那老师一定也教过欧拉函数吧？”
小红略作思考，失望地摇了摇头，说：“我没学过耶。”
“没关系的，我简单给你说说。”小明忙不迭地安慰小红，“我们已经选好了$13$和$17$两个质数，那我们算出一个$n=13×17=221$，那么欧拉函数$\varphi(n)=(13-1)×(17-1)=192$。”
小红似懂非懂地点了点头，问道：“那这个欧拉函数有什么用呢？”
小明在纸上给欧拉函数的画了一个圈，为了照顾小红，降低了语速，边写边说：“接下来，我们要找一个和$192$互质的数，记作$e$。这个$e$很好找，我们再找一个质数就行，就选$23$吧。”
见小红没有提出疑问，小明继续说：“我们再找一个数字$d$，满足$(de)\mod\varphi(n)\equiv1$，显然，我们可以对$d$取值$167$即可。”
小红似乎是有点不理解$mod$运算符，向小明询问道：“因为$167×23÷192=3841÷192=20\cdots\cdots1$，对吗？”
“没错！”小明仿佛是受到了小红的鼓励，信心满满地说，“现在我们得到了两组数字，组成一个密钥对，其中$(e,n)$是公钥，$(d,n)$是私钥。后面我甚至可以让任何一个小伙伴使用这个公钥加密信息传纸条给我，只要我不把私钥泄露出去，就是安全的。”
小红脸上泛起一抹红晕：“蜜月？”
小明似乎没发现小红的异常，继续奋笔疾书，嘴上也没闲着：“我们约定以后传递的信息都用整数，作为我们的明文。”
“这真的是我们小孩子能学会的吗？”小红感觉越来越看不透这个小明了。
加密
“是不是太难了？”小明拿出另一张草稿纸，关切地问道。
尽管觉得有点吃力，但为了后面可以安全地传纸条，小红强打精神，跟上小明的思路，边写边说：“当我的明文是‘hello’的时候，我可以通过ASCII码记录成$(104,101,108,108,111)$。但是我们以前就试过用莫尔斯码被班主任破译了，这次要怎么加密呢？”
“看我的！”小明很高兴小红可以抛出疑问，继续说道，“我们可以使用前面约定的公钥$(23,221)$对这五个数字逐个加密，即：$(104^{23}\mod 221)$, $(101^{23}\mod 221)$, $(108^{23}\mod 221)$, $(108^{23}\mod 221)$, $(111^{23}\mod 221)$，得到密文：$(26,186,218,218,2)$。”
看着一句简单的’hello’最后竟然变成了这么一个让人猜不透的密文，小红露出了满意的笑容，随即又担忧地问道：“那我要怎么解密呢？比如说，我用这个公钥给信息加密后，给你发出一段密文：$(112,111,0)$。”
解密
“小菜一碟！”没想到小红竟然给自己出题了，小明很是兴奋，奋笔疾书，“前面我们已经约定了一个私钥$(167,221)$，那可以算出加密前的内容是：$(112^{167}\mod221)$, $(111^{167}\mod221)$, $(0^{167}\mod221)$，即$ (5,2,0)$。是不是很厉害呢？”
看着小明一脸的傻乐，完全没有发现自己的弦外之音，真是枉费了自己一番心算的苦心，小红神色黯然，忍受着失望的心情，低声道：“真是个好办法呢，以后只要我们每个人都自己准备一套密钥对，就可以安全地传纸条了。”
“是啊，而且这个经验可以向全校推广，在增强同学们的计算能力的同时，又能让信息传递更安全，真是一举两得！”小明对自己的这个发明很是满意。
隐患
“但是……”小红欲言又止，仿佛担心会破坏小明的心情，怯怯地说，“既然我已经知道了你的公钥是$(e,n)$，当这个加密方法都被其他同学知道后，大家都知道你的私钥里面的$d$的求解公式就是 $d= \frac{(k×\varphi(n)+1)}{e},(k,e,d∈Z) $，不怕会被人算出来吗？”
“这是一个好问题！”小明利用扶眼镜的时间，迅速整理了一下思路，缓缓道，“这里最大的难点是计算$\varphi(n)$，但要计算出$\varphi(n)$，就必须要知道$n$是哪两个质数的乘积。因为我这里使用了$221$这个小整数，导致很容易被质因数分解算出$221=13×17$进而求出$\varphi(221)=(13-1)×(17-1)=192$，就可以使用试商的方法算出$d=\frac{(20×192)+1} {23}=167$。”
“那么？要不我们试一下用大数？增加计算难度？”小红似乎捕捉到了这个问题的关键。
“好，我试一下找两个大质数看看！”小明抖擞精神开始算起来了，“取两个大质数$p=49739,q=49999$，计算出$n=49739×49999=2486900261$，这个数字看起来比较安全了，如果要笔算的话，我都不知道要怎么下手去分解因式。”
小红还是不放心，担心地问道：“万一班主任用电脑暴力穷举怎么办？”
小明把自己想象成班主任，开始思考代码算法了，边想边说：“要破解出这两个质因子，使用试除法，就是从$2$到$\sqrt{n}$，一个一个地试验，时间复杂度就是$O(\sqrt n)$，假如我使用一个足够大的质数，结合现在的芯片运算速度来看，应该是安全的……”
“说的也是！”小红补充道，“我们可以用电脑很轻易地算出两个大质数的乘积，但是如果要对乘积进行质因数分解就很难很难，从运算时间复杂度的角度来说，我们已经赢了。”
结局
小明和小红都对这个加密方法很满意，当场敲定了各自的密钥对，并交换了彼此的公钥。然后，他们俩哼着快乐的小曲，各自回家，并暗暗下定决心，一定要好好学习，早日研究出可以快速对大数进行质因数分解的算法。