From 91845596775396914e410514ae084d5e0e0da9de Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Mon, 11 Nov 2019 20:23:50 -0500 Subject: added rsa --- final/final.tex | 2 ++ final/rsa.tex | 8 ++++++++ 2 files changed, 10 insertions(+) create mode 100644 final/rsa.tex diff --git a/final/final.tex b/final/final.tex index 4dc9c6d..1c706f9 100644 --- a/final/final.tex +++ b/final/final.tex @@ -3,6 +3,8 @@ \include Distributed Networks' History:networks +\include The RSA Algorithm:rsa + \vfil\eject\include Appendix:appendix \bye diff --git a/final/rsa.tex b/final/rsa.tex new file mode 100644 index 0000000..0b2962e --- /dev/null +++ b/final/rsa.tex @@ -0,0 +1,8 @@ +In determining correctness, a major concern is determining that the message hasn't been tampered with by an intelligent intermediate. +Public key cryptography tries to answer this problem by providing proof of authorship and, as an extension of ``normal'' encryption, preventing interception. +RSA is one such algorithm. +It works by providing a set of public keys to all parties, and corresponding secret private keys. + +One of the simpler algorithms, it applies the NP-hard nature of factorizing a semiprime, Euler’s theorem, and the Euclidean Algorithm to encrypt communication. +Because it is simple to devise, it has been included as a sample, in the form of a Python script which encrypts and decrypts messages, given a small RSA key (compared to those used in real applications). +There are several optimizations (such as applying the Chinese Remainder Theorem) which can be used, but none have been applied to maintain the code's simplicity. -- cgit From 2c8c55cd0511169f9f02a49be79c58d3c02cdc11 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Mon, 11 Nov 2019 20:57:43 -0500 Subject: added pre command --- format.tex | 3 +++ 1 file changed, 3 insertions(+) diff --git a/format.tex b/format.tex index 4668b2e..1fa9d04 100644 --- a/format.tex +++ b/format.tex @@ -37,3 +37,6 @@ Livshyts %% Modular Sections \def\include#1:#2\par{\section #1\par\par\input #2\relax} \def\sinclude#1:#2\par{\subsection #1\par\par\input #2\relax} + +%% Bullet Points and Numbering +\def\pre#1{\par\leavevmode\llap{\hbox to \parindent{\hfil #1 \hfil}}} -- cgit 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 ++++++++++++++++ final/rsa.tex | 5 ++++- 2 files changed, 20 insertions(+), 1 deletion(-) create mode 100644 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. diff --git a/final/rsa.tex b/final/rsa.tex index 0b2962e..837a00e 100644 --- a/final/rsa.tex +++ b/final/rsa.tex @@ -1,8 +1,11 @@ In determining correctness, a major concern is determining that the message hasn't been tampered with by an intelligent intermediate. Public key cryptography tries to answer this problem by providing proof of authorship and, as an extension of ``normal'' encryption, preventing interception. -RSA is one such algorithm. +RSA (Rivest-Shamir-Adleman, named after its MIT faculty creators) is one such algorithm. It works by providing a set of public keys to all parties, and corresponding secret private keys. One of the simpler algorithms, it applies the NP-hard nature of factorizing a semiprime, Euler’s theorem, and the Euclidean Algorithm to encrypt communication. Because it is simple to devise, it has been included as a sample, in the form of a Python script which encrypts and decrypts messages, given a small RSA key (compared to those used in real applications). There are several optimizations (such as applying the Chinese Remainder Theorem) which can be used, but none have been applied to maintain the code's simplicity. + +\sinclude Methodology:rsa-method + -- cgit From 6ab2b7bfe213626415a4c1b63451e4889c4d88f4 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Mon, 11 Nov 2019 21:04:30 -0500 Subject: removed RSAALGO --- final/RSAAlgorithm.pdf | Bin 47174 -> 0 bytes 1 file changed, 0 insertions(+), 0 deletions(-) delete mode 100644 final/RSAAlgorithm.pdf diff --git a/final/RSAAlgorithm.pdf b/final/RSAAlgorithm.pdf deleted file mode 100644 index 37072e1..0000000 Binary files a/final/RSAAlgorithm.pdf and /dev/null differ -- cgit From 290603c1d683e63b2e73eebc8f07f3e5386fd9e0 Mon Sep 17 00:00:00 2001 From: SpaceOddity404 <40719093+SpaceOddity404@users.noreply.github.com> Date: Mon, 11 Nov 2019 21:27:35 -0500 Subject: Add files via upload --- final/RSA.py | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) create mode 100644 final/RSA.py diff --git a/final/RSA.py b/final/RSA.py new file mode 100644 index 0000000..c12e94f --- /dev/null +++ b/final/RSA.py @@ -0,0 +1,33 @@ +import random +def isPrime(x): + pr = True + for j in range(2, x): + if x % j == 0: + pr = False + return pr +def remove_char(input_string, index): + first_part = input_string[:index] + second_part - input_string[index+1:] + return first_part + second_part +primes = [i for i in range(2,1000) if isPrime(i)] +p = random.choice(primes) +q = random.choice(primes) +n = p * q +print(n) +string = input() +sepChars = list(string) +numChars = 0 +for c in sepChars: + numChars += ((128**sepChars.index(c))*ord(c)) +print(numChars) +blocks = [] +c = 0 +for j in range(0, n-1): + blocks.append(str(numChars)[j:j+1]) +for j in range(n-1, len(str(numChars))): + blocks[(len(str(n))-1)%j] = blocks[(len(str(n))-1)%j] + str(numChars)[j:j+1] + +print(blocks) + + + -- cgit