Merge branch 'master' of https://github.com/feynmansfedora/appcomb-proj

7 files changed, 77 insertions, 14 deletions

diff --git a/final/RSA.py b/final/RSA.py
index c12e94f..82a3211 100644
--- a/final/RSA.py
+++ b/final/RSA.py
@@ -1,4 +1,5 @@
 import random
+from math import gcd as bltin_gcd
 def isPrime(x):
     pr = True
     for j in range(2, x):
@@ -9,25 +10,33 @@ def remove_char(input_string, index):
     first_part = input_string[:index]
     second_part - input_string[index+1:]
     return first_part + second_part
+def coprime(a, b):
+    return bltin_gcd(a, b) == 1
+
 primes = [i for i in range(2,1000) if isPrime(i)]
 p = random.choice(primes)
 q = random.choice(primes)
 n = p * q
-print(n)
+coprimes = [j for j in range(2,n) if coprime(j, ((p-1)*(q-1)))]
+e = random.choice(coprimes)
 string = input()
 sepChars = list(string)
 numChars = 0
+
 for c in sepChars:
     numChars += ((128**sepChars.index(c))*ord(c))
-print(numChars)
-blocks = []
+print("numChars:",numChars)
 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]
+blocks = []
 
-print(blocks)
-    
+while numChars > 0:
+    blocks.append(numChars%n)
+    numChars = (numChars-numChars%n)/n
+
+print("Blocks:",blocks)
+encryptedBlocks = []
+for b in blocks:
+    encryptedBlocks.append((b**e)%n)
+print("Encrypted:",encryptedBlocks)
     
     
diff --git a/final/appendix.tex b/final/appendix.tex
index 2dc9741..f67d2d6 100644
--- a/final/appendix.tex
+++ b/final/appendix.tex
@@ -1,9 +1,10 @@
-These programs, {\tt rsa.py} and {\tt bridges.py} need to be run with Python3, so install that as suggested by \link{https://www.python.org/downloads/}.
+These programs, need to be run with Python3, so install that as suggested by \link{https://www.python.org/downloads/}.
 The package manager {\tt pip} is also necessary for installation of third party graphics libraries such as {\tt NetworkX}. Install that as described here: \link{https://pip.pypa.io/en/stable\-/installing/}.
 
 Now that those tools are available, run the following shell commands to install relevant libraries:
 {\tt\obeylines\parindent=1in
 \$ pip install networkx
+\$ pip install numpy
 }
 
-Each file should be executable with ``{\tt python3 \$filename}''.
+Each file should be executable with ``{\tt python3 \$filename}'', preferably in its local directory. The files can be obtained from the internet with ``{\tt git clone https://github.com/feynmansfedora/appcomb-proj.git}'', assuming {\tt git} is installed. If it is not, it can be cloned from \link{https://github.com/feynmansfedora/appcomb-proj} directly.
diff --git a/final/final.pdf b/final/final.pdf
index 2be7a9e..889c90f 100644
--- a/final/final.pdf
+++ b/final/final.pdf
diff --git a/final/networks.tex b/final/networks.tex
index 9f6a9e6..710b84e 100644
--- a/final/networks.tex
+++ b/final/networks.tex
@@ -1,6 +1,6 @@
 Distributed networking describes a number of protocols, systems, and technologies.
 The most popular amongst them is ``the internet,'' to the extent it can be described as a single entity.
-It originates in very centralized institutions: MIT and DARPA, who invented packet switching, a way of transferring data across a group of nodes [POTENTIAL SUBTOPIC?]\footnote{$^1$}{\link{https://networkencyclopedia.com/packet-switching/}}\footnote{$^2$}{\link{https://www.internetsociety.org/internet/history-internet/brief-history-internet/}}.
+It originates in very centralized institutions: MIT and DARPA, who invented packet switching, a way of transferring data across a group of nodes \footnote{$^1$}{\link{https://networkencyclopedia.com/packet-switching/}}\footnote{$^2$}{\link{https://www.internetsociety.org/internet/history-internet/brief-history-internet/}}.
 Packet switching was the birth of the internet, and as such is a central theme of our project.
 
 The way that packets (any information transferred across any protocol) maintain their correctness, or proving that the data is untampered, and the way that computers connect to eachother will be explored in this paper.
diff --git a/final/rsa-decrypt.py b/final/rsa-decrypt.py
new file mode 100644
index 0000000..39a2720
--- /dev/null
+++ b/final/rsa-decrypt.py
@@ -0,0 +1,29 @@
+encrypted = [340, 316, 145, 278, 250, 435, 321, 109, 115, 490, 156, 212, 122, 288, 287, 164, 225] # Directly from demo output of encrypted
+p = int(input('prime 1: '))
+q = int(input('prime 2: '))
+n = p*q
+tot = (p-1)*(q-1)
+e = int(input('e: '))
+
+# Calculate d such that ed == 1 mod tot
+d = 1 # Guess
+while (e*d % tot != 1):
+  d += 1
+# Algorithm is currently extremely dumb
+
+def decrypt_block(blk):
+  return blk**d % n
+
+decrypted = [decrypt_block(block) for block in encrypted]
+
+messagenum = 0
+for blockind in range(len(decrypted)):
+  block = decrypted[blockind]
+  messagenum += block * n ** blockind
+
+message = ''
+while messagenum > 0:
+  message = chr(messagenum%128) + message
+  messagenum = (messagenum-messagenum%128)//128
+
+print(message)
diff --git a/final/rsa-encrypt.py b/final/rsa-encrypt.py
new file mode 100644
index 0000000..a15fe9d
--- /dev/null
+++ b/final/rsa-encrypt.py
@@ -0,0 +1,24 @@
+'''p = 29
+q = 17
+n = p*q
+tot = (p-1)*(q-1)
+e = 3 # Many present strictly for convenience's sake'''
+n = int(input('n: '))
+e = int(input('e (make sure it\'s relatively prime to p-1 and q-1): '))
+
+message = input('message:\n')
+messagenum = 0
+for char in message:
+  messagenum += ord(char)
+  messagenum *= 128 # Assuming ASCII only characters
+
+messageblocks = []
+while messagenum > 0:
+  messageblocks.append(messagenum%n)
+  messagenum = (messagenum-messagenum%n)//n
+
+def encrypt_block(blk):
+  return (blk ** e) % n
+
+encrypted = [encrypt_block(block) for block in messageblocks]
+print(encrypted)
diff --git a/final/rsa-method.tex b/final/rsa-method.tex
index bf75cd0..69bf4b1 100644
--- a/final/rsa-method.tex
+++ b/final/rsa-method.tex
@@ -1,4 +1,4 @@
-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. 
+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.\footnote{$^3$}{\link{https://primes.utm.edu/glossary/page.php?sort=RSA}}
 
 \def\mod#1{\thinspace(mod\thinspace #1)}
 \noindent Encryption is accomplished through the following three steps:
@@ -6,7 +6,7 @@ The encryption process begins with the selection of two large primes, $p$ and $q
 \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{1.}  Calculate an integer $d$ such that $de \equiv 1 \mod{\phi(n)}$ using the Euclidean algorithm. Note that $\phi(n)$ is the totient function, or the number of non-coprime integers with $n$ less than $n$.
 \pre{2.}  Convert back using $B \equiv C^d \mod{n}$.
 
 The decryption process described above makes use of Euler’s theorem.