\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{interval}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年6月2日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\lstset{basicstyle=\ttfamily}

\begin{document}

\section{RSA算法}

取定一个字符集$\Sigma$为字母加空格，共27个字符，从Alice发送一个密文$M$到Bob，需要一个加密函数$N=E(M)$，对于Bob，其需要一个解密函数$M=D(N)$，最终得到原来的明文

比较简单的方式是对称加密，即双方使用相同的密钥，但这需要这种密钥为私钥，而只要破解了密钥之后，该算法就被破解了

而假如可以实现将加解密分隔开，这样即使知道了加密函数，依然无法得到解密函数

RSA算法就是这样一种算法，其基于数论

首先找到两个互不相等的大素数$p$和$q$，计算$n=pq$，再找到和$\phi(n)=(p-1)(q-1)$互素的小奇数$e$，计算$ed\equiv1\mod \phi(n)$，则公钥$(e,n)$，私钥$(d,n)$.
加密函数$P(M)=M^e\mod n$，解密函数$S(C)=C^d\mod n$

那么是否有加密函数与解密算法互为逆呢？即$S(P(M))=M,P(S(N))=N$？前式验证$P$为单射，后式验证$P$是满射，则如果两式成立，则$P$为双射，即$P$为可逆函数，$S$为对应的逆函数.

根据欧拉公式，如果$\gcd(M,n)=1$，有$M^{\phi(n)}\equiv1\mod n$，则$M^{ed}\equiv M^{k\phi(n)}\cdot M\equiv M\mod n$，否则
要么$p|M$要么$q|M$，不妨假设$M=lp$，有$p|M^{ed}-M$，只要证$q|M^{ed}-M$，即$M^{ed}\equiv M\mod q$，此时有$\gcd(M,q)=1$，则$M^{ed}\equiv M^{k(p-1)\phi(q)}\cdot M\equiv M\mod q$，得证$n=pq|M^{ed}-M$，$M^{ed}\equiv M\mod n$.

\end{document}