RSA code: Difference between revisions
(→Icon and Unicon: alternate version per talk and GO) |
m (→{{header|Icon}} and {{header|Unicon}}: n not d+1) |
||
Line 80: | Line 80: | ||
write("RSA Demo using\n e=",e,"\n d=",d,"\n n=",n) |
write("RSA Demo using\n e=",e,"\n d=",d,"\n n=",n) |
||
toobig := repl("x",*decode( |
toobig := repl("x",*decode(n)) |
||
every m := !["Rosetta Code", "Hello Word!", toobig] do { |
every m := !["Rosetta Code", "Hello Word!", toobig] do { |
||
write("\nMessage = ",image(m)) |
write("\nMessage = ",image(m)) |
||
Line 139: | Line 139: | ||
Message = "xxxxxxxxxxxxxxxxxx" |
Message = "xxxxxxxxxxxxxxxxxx" |
||
Encoded = 10494468328720293243075632128305111296931960 |
Encoded = 10494468328720293243075632128305111296931960 |
||
** Failed message too large ** |
** Failed message too large ** |
||
</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |
Revision as of 12:23, 27 April 2011
Given an RSA key (n,e,d), construct a program to encrypt and decrypt plaintext messages strings. A brief description of RSA is as follows:
RSA code is used to encode secret messages. It is named after the 3 men who first published it, Rivest, Shamir, and Adleman. The advantage of this type of encryption is that you can distribute the number “” and “” (which make up the encryption key) to everyone. The decryption key “” is kept secret, so only you and a select few can read the encrypted plaintext. The process by which this is done is that a message, for example “Hello World” is converted to numbers (). This yields a string of numbers, generally referred to as "numerical plaintext", “”. For this example, “Hello World” with , would be . The plaintext is split into blocks because no one block can be larger than the value of , else the decryption will fail. The ciphertext, , is then computed by taking each block of , and computing
Similarly, to decode, one computes
To generate a key, one finds 2 (ideally large) primes and . the value “” is simply: . One must then choose an “” such that . That is to say, and are relatively prime to each other. The decryption value is then found by solving
It is important to note that a numerical plaintext block cannot be greater than the value of “”, else decryption will not find the correct values due to the presence of the . Also important is that the security of the code is based off the secrecy of the decryption exponent “”, and therefor is based off the difficulty in factoring “”.
Go
<lang go>package main
import (
"big" "fmt"
)
func main() {
var n, e, d, bb, ptn, etn, dtn big.Int pt := "Rosetta Code" fmt.Println("Plain text: ", pt)
// a key set big enough to hold 16 bytes of plain text in // a single block (to simplify the example) and also big enough // to demonstrate efficiency of modular exponentiation. n.SetString("9516311845790656153499716760847001433441357", 10) e.SetString("65537", 10) d.SetString("5617843187844953170308463622230283376298685", 10)
// convert plain text to a number for _, b := range []byte(pt) { ptn.Or(ptn.Lsh(&ptn, 8), bb.SetInt64(int64(b))) } fmt.Println("Plain text as a number:", &ptn)
// encode a single number etn.Exp(&ptn, &e, &n) fmt.Println("Encoded: ", &etn)
// decode a single number dtn.Exp(&etn, &d, &n) fmt.Println("Decoded: ", &dtn)
// convert number to text var db [16]byte dx := 16 bff := big.NewInt(0xff) for dtn.BitLen() > 0 { dx-- db[dx] = byte(bb.And(&dtn, bff).Int64()) dtn.Rsh(&dtn, 8) } fmt.Println("Decoded number as text:", string(db[dx:]))
}</lang> Output:
Plain text: Rosetta Code Plain text as a number: 25512506514985639724585018469 Encoded: 916709442744356653386978770799029131264344 Decoded: 25512506514985639724585018469 Decoded number as text: Rosetta Code
Icon and Unicon
Please read talk pages.
<lang Icon>procedure main() # rsa demonstration
n := 9516311845790656153499716760847001433441357 e := 65537 d := 5617843187844953170308463622230283376298685 write("RSA Demo using\n e=",e,"\n d=",d,"\n n=",n) toobig := repl("x",*decode(n)) every m := !["Rosetta Code", "Hello Word!", toobig] do { write("\nMessage = ",image(m)) write( "Encoded = ",m := encode(m)) m := rsa(m,e,n) | (write("** Failed message too large **") & next) write( "Encrypt = ",m) write( "Decrypt = ",m := rsa(m,d,n)) write( "Decoded = ",image(decode(m))) }
end
procedure mod_power(base, exponent, modulus) # fast modular exponentation
result := 1 while exponent > 0 do { if exponent % 2 = 1 then result := (result * base) % modulus exponent /:= 2 base := base ^ 2 % modulus } return result
end
procedure rsa(text,e,n) # return rsa encryption of numerically encoded message; fail if text < n return mod_power(text,e,text < n) end
procedure encode(text) # numerically encode ascii text as int
every (message := 0) := ord(!text) + 256 * message return message
end
procedure decode(message) # numerically decode int to ascii text
text := "" while text ||:= char((0 < message) % 256) do message /:= 256 return reverse(text)
end</lang>
Output:
RSA Demo using e=65537 d=5617843187844953170308463622230283376298685 n=9516311845790656153499716760847001433441357 Message = "Rosetta Code" Encoded = 25512506514985639724585018469 Encrypt = 916709442744356653386978770799029131264344 Decrypt = 25512506514985639724585018469 Decoded = "Rosetta Code" Message = "Hello Word!" Encoded = 87521618088882533792113697 Encrypt = 1798900477268307339588642263628429901019383 Decrypt = 87521618088882533792113697 Decoded = "Hello Word!" Message = "xxxxxxxxxxxxxxxxxx" Encoded = 10494468328720293243075632128305111296931960 ** Failed message too large **
J
<lang j>NB. keys N=: 2537x E=: 13x D=: 937x
NB. blocks letters=: 'abcdefghijklmnopqrstuvwxyz,.!? ' base=: 1+#letters blocksize=: base <.@^. N pad=: base ?@#~ blocksize | -@# txt2num=: ((-blocksize) base&#.\ 1x + letters&i. , pad) :.num2txt num2txt=: ((' ',letters) {~ ,@:#:~&(blocksize#base) ) :.txt2num
NB. RSA algorithm cypher=: N&|@^ encrypt=: cypher&E@txt2num decrypt=: num2txt@:cypher&D</lang>
Note: letters
lists 31 distinct letters, so base
will be 32. And, with the value for N, blocksize
will be 2. pad
will add random garbage letters onto the end of the message if needed, so that the padded message length is an even multiple of base
. Finally, txt2num will convert a message into a sequence of numbers whose length is the padded message length divided by blocksize, and num2txt will convert a sequence of numbers back into a padded message.
Example use:
<lang j> txt2num 'hi there' 265 1012 261 581
encrypt 'hi there'
695 153 2377 260
decrypt 695 153 2377 260
hi there</lang>
Alternatively, here's a workalike for the current Go implementation:
<lang j> N=: 9516311845790656153499716760847001433441357x
E=: 65537x D=: 5617843187844953170308463622230283376298685x ] text=: 'Rosetta Code'
Rosetta Code
] num=: 256x #. a.i.text
25512506514985639724585018469
] enc=: N&|@^&E num
916709442744356653386978770799029131264344
] dec=: N&|@^&D enc
25512506514985639724585018469
] final=: a. {~ 256x #.inv dec
Rosetta Code</lang>
Note: as indicated at http://www.jsoftware.com/help/dictionary/special.htm, N&|@^
does not bother with creating the exponential intermediate result.
Python
This code will open up a simple Tkinter window which has space to type a message. That message can then be encrypted by pressing the button labeled "encrypt". It will then print an output of ciphertext blocks, separated by commas. To decrypt a message, simply press the decrypt button. All ciphertext data must be entered with each block separated by commas. The ciphertext always goes (and appears) in the bottom box, while plaintext goes (and appears) in the topmost box. Upon decryption, random letters may have been appended to the end of the message, this is an aspect of the code to ensure the final block of plaintext is not a single letter, for example, a, 01, encoded is 01 (which means this letter was transmitted in the open!).
This code was made just for fun, feel free to suggest anything to make it better. The key given here is a toy key, it is easily broken. --Erasmus 04:23, 24 March 2011 (UTC) <lang python>from tkinter import * import random import time
letter = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q",
"r","s","t","u","v","w","x","y","z",",",".","!","?",' ']
number = ["01","02","03","04","05","06","07","08","09","10","11","12","13",
"14","15","16","17","18","19","20","21","22","23","24","25","26","27", "28","29","30",'31']
n = 2537 e = 13 d = 937 def decrypt(F,d):
# performs the decryption function on an block of ciphertext if d == 0: return 1 if d == 1: return F w,r = divmod(d,2) if r == 1: return decrypt(F*F%n,w)*F%n else: return decrypt(F*F%n,w)
def correct():
# Checks to see if the numerical ciphertext block should have started with a 0 (by seeing if the 0 is missing), if it is, it then adds the 0. # example - 0102 is output as 102, which would lead the computer to think the first letter is 10, not 01. This ensures this does not happen. for i in range(len(D)): if len(str(P[i]))%2 !=0: y = str(0)+str(P[i]) P.remove(str(P[i])) P.insert(i,y)
def cipher(b,e):
# Performs the Encryption function on a block of ciphertext if e == 0: return 1 if e == 1: return b w,r = divmod(e,2) if r == 1: return cipher(b*b%n,w)*b%n else: return cipher(b*b%n,w)
def group(j,h,z):
# Places the plaintext numbers into blocks for encryption for i in range(int(j)): y = 0 for n in range(h): y += int(numP[(h*i)+n])*(10**(z-2*n)) X.append(int(y))
class App:
# Creates a Tkineter window, for ease of operation def __init__(self, master):
frame = Frame(master) frame.grid()
#create a button with the quit command, and tell it where to go quitbutton = Button(frame, text = "quit", fg ="red", command = root.quit, width = 10) quitbutton.grid(row = 0, column =3)
#create an entry box, tell it where it goes, and how large it is entry = Entry(frame, width = 100) entry.grid(row = 0, column = 0)
#set initial content of the entry box self.contents = StringVar() self.contents.set("Type message here") entry["textvariable"] = self.contents
# Create a button which initializes the decryption of ciphertext decrypt = Button(frame,text = "Decrypt", fg = "blue", command = self.Decrypt) decrypt.grid(row = 2, column = 1)
#create a label to display the number of ciphertext blocks in an encoded message label = Label(frame, text = "# of blocks") label.grid(row = 1, column = 1)
#creates a button which initializes the encryption of plaintext encrypt = Button(frame, text="Encrypt", fg = "blue", command = self.Encrypt) encrypt.grid(row =0, column =1)
#create an entry box for the value of "n" nbox = Entry(frame, width = 100) nbox.grid(row = 3, column = 0)
self.n = StringVar() self.n.set(n) nbox["textvar"] = self.n nbox.bind('<Key-Return>', self.set_n) #key binding, when you press "return", the value of "n" is changed to the value now in the box
nlabel = Label(frame, text = "the value of 'n'") nlabel.grid(row = 3, column = 1)
#create an entry box for the value of "e" ebox = Entry(frame, width = 100) ebox.grid(row = 4, column = 0)
self.e = StringVar() self.e.set(e) ebox["textvar"] = self.e ebox.bind('<Key-Return>', self.set_e)
elabel = Label(frame, text = "the value of 'e'") elabel.grid(row = 4, column = 1)
#create an entry box for the value of "d" dbox = Entry(frame, width = 100) dbox.grid(row =5, column = 0)
self.d = StringVar() self.d.set(d) dbox["textvar"] = self.d dbox.bind('<Key-Return>', self.set_d)
dlabel = Label(frame, text = "the value of 'd'") dlabel.grid(row = 5, column =1)
blocks = Label(frame, width = 100) blocks.grid(row = 1, column =0)
self.block = StringVar() self.block.set("number of blocks") blocks["textvar"] = self.block output = Entry(frame, width = 100) output.grid(row = 2, column = 0)
self.answer = StringVar() self.answer.set("Ciphertext") output["textvar"] = self.answer
# The commands of all the buttons are defined below def set_n(self,event): global n n = int(self.n.get()) print("n set to", n)
def set_e(self, event): global e e = int(self.e.get()) print("e set to",e)
def set_d(self,event): global d d = int(self.d.get()) print("d set to", d) def Decrypt(self): #decrypts an encoded message global m,P,D,x,h,p,Text,y,w,PText P = [] D = str(self.answer.get()) #Pulls the ciphertext out of the ciphertext box D = D.lstrip('[') #removes the bracket "[" from the left side of the string D = D.rstrip(']') D = D.split(',') #splits the string into a list of strings, separating at each comma. for i in range(len(D)): #decrypts each block in the list of strings "D" x = decrypt(int(D[i]),d) P.append(str(x)) correct() #ensures each block is not missing a 0 at the start h = len(P[0]) p = [] for i in range(len(D)): #further separates the list P into individual characters, i.e. "0104" becomes "01,04" for n in range(int(h/2)): p.append(str(P[i][(2*n):((2*n)+2)])) # grabs every 2 character group from the larger block. It gets characters between 2*n, and (2*n)+2, i.e. characters 0,1 then 2,3 etc... Text = [] for i in range(len(p)): # converts each block back to text characters for j in range(len(letter)): if str(p[i]) == number[j]: Text.append(letter[j]) PText = str() for i in range(len(Text)): #places all text characters in one string PText = PText + str(Text[i]) self.contents.set(str(PText)) #places the decrypted plaintext in the plaintext box
def Encrypt(self): #encrypts a plaintext message using the current key global plaintext,numP,q,j,z,X,C plaintext = self.contents.get() #pulls the plaintext out of the entry box for use plaintext = plaintext.lower() #places all plaintext in lower case numP = [] for i in range(len(plaintext)): # converts letters and symbols to their numerical values for j in range(len(letter)): if plaintext[i] == letter[j]: numP.append(number[j]) h = (len(str(n))//2)-1 # This sets the block length for the code in question, based on the value of "n" q = len(numP)%h for i in range(h-q): numP.append(number[random.randint(0,25)]) # Ensures the final block of plaintext is filled with letters, and is not a single orphaned letter. j = len(numP) / h X = [] z = 0 for m in range(h-1): z+=2 group(j,h,z) # This sets the numerical plaintext into blocks of appropriate size, and places them in the list "X" k = len(X) C = [] for i in range(k): # performs the cipher function for each block in the list of plaintext blocks b = X[i] r = cipher(b,e) C.append(r) self.answer.set(C) self.block.set(len(C)) #places the ciphertext into the ciphertext box
root = Tk()
app = App(root)
root.mainloop() root.destroy()</lang>
Alternatively, a version without the tkinter window, which uses the same components as the program above, only without the Tkinter interface.
<lang python>import random import time
def decrypt(F,d):
if d == 0: return 1 if d == 1: return F w,r = divmod(d,2) if r == 1: return decrypt(F*F%n,w)*F%n else: return decrypt(F*F%n,w)
def correct():
for i in range(len(C)): if len(str(P[i]))%2 !=0: y = str(0)+str(P[i]) P.remove(str(P[i])) P.insert(i,y)
def cipher(b,e):
if e == 0: return 1 if e == 1: return b w,r = divmod(e,2) if r == 1: return cipher(b*b%n,w)*b%n else: return cipher(b*b%n,w)
def group(j,h,z):
for i in range(int(j)): y = 0 for n in range(h): y += int(numP[(h*i)+n])*(10**(z-2*n)) X.append(int(y))
def gcd(a, b):
while b != 0: (a, b) = (b, a%b) return a
letter = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q",
"r","s","t","u","v","w","x","y","z",",",".","!","?"," "]
number = ["01","02","03","04","05","06","07","08","09","10","11","12","13",
"14","15","16","17","18","19","20","21","22","23","24","25","26","27", "28","29","30","31"]
print( '\n' )
def Decrypt():
#decrypts an encoded message global m,P,C,x,h,p,Text,y,w P = [] C = str(input("Enter ciphertext blocks:")) C = C.lstrip('[') C = C.rstrip(']') C = C.split(',') for i in range(len(C)): x = decrypt(int(C[i]),d) P.append(str(x)) correct() #print(P) h = len(P[0]) p = [] for i in range(len(C)): for n in range(int(h/2)): p.append(str(P[i][(2*n):((2*n)+2)])) Text = [] for i in range(len(p)): for j in range(len(letter)): if str(p[i]) == number[j]: Text.append(letter[j]) PText = str() for i in range(len(Text)): PText = PText + str(Text[i]) print("Plaintext is:", PText)
def Encrypt():
#encrypts a plaintext message using the current key global plaintext,numP,q,j,z,X,C plaintext =(input("Enter Plaintext :")) plaintext = plaintext.lower() numP = [] for i in range(len(plaintext)): for j in range(len(letter)): if plaintext[i] == letter[j]: numP.append(number[j]) h = (len(str(n))//2)-1 q = len(numP)%h for i in range(h-q): numP.append(number[random.randint(0,25)]) j = len(numP) / h #print(numP) X = [] z = 0 for m in range(h-1): z+=2 group(j,h,z) k = len(X) C = [] for i in range(k): b = X[i] r = cipher(b,e) C.append(r) print("Ciphertext:",C) print("Number of Ciphertext blocks:",len(C))
def setup():
global n,e,d while True: try: n = int(input(" Enter a value for n :")) if n > 2: break except ValueError: print('please enter a number') while 1!=2 : try: e = int(input(" Enter a value for e :")) if e >= 2: break except ValueError: print('please enter a number') while True: try: d = int(input(" Enter a value for d. If d unknown, enter 0 :")) if d >= 0: break except ValueError: print('please enter a number')
- setup()
n = 2537 e = 13 d = 937
print("To redefine n,e, or d, type 'n','e',... etc.") print("To encrypt a message with the current key, type 'Encrypt'") print("To decrypt a message with the current key, type 'Decrypt'") print("Type quit to exit") print( '\n' ) print( '\n' )
mm = str() while mm != 'quit':
mm = input("Enter Command...") if mm.lower() == 'encrypt': Encrypt() elif mm.lower() == 'decrypt': Decrypt() elif mm.lower() == 'n': try: print('current n = ',n) n = int(input(" Enter a value for n :")) except ValueError: print('That is not a valid entry') elif mm.lower() == 'help': print("To redefine n,e, or d, type 'n','e',... etc.") print("To encrypt a message with the current key, type 'Encrypt'") print("To decrypt a message with the current key, type 'Decrypt'") print("Type quit to exit") print( '\n' ) print( '\n' ) elif mm.lower() == 'e': try: print('current e = ',e) e = int(input(" Enter a value for e :")) except ValueError: print('That is not a valid entry') elif mm.lower() == 'd': try: print('current d = ',d) d = int(input(" Enter a value for d :")) except ValueError: print('That is not a valid entry') else: if mm != 'quit': ii= random.randint(0,6) statements = ["I sorry, Dave. I'm afraid i can't do that","I'm begging you....read the directions","Nah ahh ahh, didnt say the magic word","This input is....UNACCEPTABLE!!","Seriously....was that even a word???","Please follow the directions","Just type 'help' if you are really that lost"] print(statements[ii])</lang>
Example use :
Any entered commands are not case sensitive, nor is the plaintext input. Commands must be spelled correctly. Ciphertext blocks are input all at once, but must be separated by commas. When decrypted, there may be random letters attached to the end of the message. The program does this in order to fill blocks completely, and not have orphaned characters. <lang python>>>> To redefine n,e, or d, type 'n','e',... etc. To encrypt a message with the current key, type 'Encrypt' To decrypt a message with the current key, type 'Decrypt' Type quit to exit
Enter Command...ENCRYPT
Enter Plaintext :drink MORE Ovaltine
Ciphertext: [140, 2222, 1864, 1616, 821, 384, 2038, 2116, 2222, 205, 384, 2116, 45, 1, 2497, 793, 1864, 1616, 205, 41]
Number of Ciphertext blocks: 20
Enter Command...decrypt
Enter ciphertext blocks:[140, 2222, 1864, 1616, 821, 384, 2038, 2116, 2222, 205, 384, 2116, 45, 1, 2497, 793, 1864, 1616, 205, 41]
Plaintext is: drink more ovaltineu
Enter Command...quit
>>> </lang>