From a27be593369869d43a9da2d47fd68bef97473fca Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Mon, 11 Nov 2019 20:58:03 -0500 Subject: included some RSA specifics --- final/rsa-method.tex | 16 ++++++++++++++++ 1 file changed, 16 insertions(+) create mode 100644 final/rsa-method.tex (limited to 'final/rsa-method.tex') diff --git a/final/rsa-method.tex b/final/rsa-method.tex new file mode 100644 index 0000000..bf75cd0 --- /dev/null +++ b/final/rsa-method.tex @@ -0,0 +1,16 @@ +The encryption process begins with the selection of two large primes, $p$ and $q$, their product $n=pq$, and a fourth number $e$ relatively prime to $\phi(n)$. $n$ is public, whereas $p$ and $q$ are secret. + +\def\mod#1{\thinspace(mod\thinspace #1)} +\noindent Encryption is accomplished through the following three steps: +\pre{1.} Convert message to a number (like {\tt a} becomes $1$ and {\tt ab} becomes $130$, assuming a 128-character language) +\pre{2.} Break the converted message into blocks of size less than $n$. +\pre{3.} For each block B, an encrypted block C is created such that $$C \equiv B^e\thinspace(mod\thinspace n)$$. +\noindent To decrypt that message: +\pre{1.} Calculate an integer $d$ such that $de \equiv 1 \mod{\phi(n)}$ using the Euclidean algorithm. +\pre{2.} Convert back using $B \equiv C^d \mod{n}$. + +The decryption process described above makes use of Euler’s theorem. +Some decryption algorithms make use of other mathematical theorems of relation, including the Chinese Remainder Theorem. + +The RSA Algorithm, while nearly unbreakable, isn’t as untouchable as originally thought, shown by the example number $n=pq$ that Rivest, Shamir, and Adleman published as a challenge in ‘77 was broken in ‘94. +This proves that as computing power grows, the best cryptographers can do is increase the size of the secrets to make prime factorization as difficult as possible, or its analogue in more arcane algorithms. -- cgit