RSA code: Difference between revisions
(J: give blocking example) |
m (→{{header|Wren}}: Minor tidy) |
||
(126 intermediate revisions by 50 users not shown) | |||
Line 1: | Line 1: | ||
{{ |
{{task|Encryption}} |
||
Given an [[wp:RSA|RSA]] key (n,e,d), construct a program to encrypt and decrypt plaintext messages strings. |
|||
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 "n" and "e" (which make up the encryption key) to everyone. The decryption key "d" 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 (a=01,b=02,...,z=26). This yields a string of numbers, generally referred to as "numerical plaintext", or "P". For this example, "Hello World" with n = 2537, would be [805, 1212, 1523, 1518, 1204]. The plaintext is split into blocks because no one block can be larger than the value of n, else the decryption will fail. The ciphertext, C, is then computed by taking each block of P, and computing C ≡ P^e mod(n). Similarly, to decode, one computes P ≡ C^d mod(n). |
|||
'''Background''' |
|||
To generate a key, one finds 2 (large) primes p and q. the value "n" is simply: n = p*q. |
|||
One must then choose an "e" such that gcd(e, (p-1)*(q-1) ) = 1. That is to say, e and (p-1)*(q-1) are relatively prime to each other. |
|||
The decryption value d is then found by solving d*e ≡ 1 mod((p-1)*(q-1)) |
|||
RSA code is used to encode secret messages. It is named after Ron Rivest, Adi Shamir, and Leonard Adleman who published it at MIT in 1977. The advantage of this type of encryption is that you can distribute the number “<math>n</math>” and “<math>e</math>” (which makes up the Public Key used for encryption) to everyone. The Private Key used for decryption “<math>d</math>” is kept secret, so that only the recipient can read the encrypted plaintext. |
|||
It is important to note that a numerical plaintext block cannot be greater than the value of "n", else decryption will not find the correct values due to the presence of the mod(n). |
|||
Also important is that the security of the code is based off the secrecy of the decryption exponent "d", and therefor is based off the difficulty in factoring "n". |
|||
The process by which this is done is that a message, for example “Hello World” is encoded as numbers (This could be encoding as ASCII or as a subset of characters <math>a=01,b=02,...,z=26</math>). This yields a string of numbers, generally referred to as "numerical plaintext", “<math>P</math>”. For example, “Hello World” encoded with a=1,...,z=26 by hundreds would yield <math>0805 1212 1523 1518 1204</math>. |
|||
The plaintext must also be split into blocks so that the numerical plaintext is smaller than <math>n</math> otherwise the decryption will fail. |
|||
The ciphertext, <math>C</math>, is then computed by taking each block of <math>P</math>, and computing |
|||
: <math>C \equiv P^e \mod n</math> |
|||
Similarly, to decode, one computes |
|||
: <math>P \equiv C^d \mod n</math> |
|||
To generate a key, one finds 2 (ideally large) primes <math>p</math> and <math>q</math>. the value “<math>n</math>” is simply: <math>n = p \times q</math>. |
|||
One must then choose an “<math>e</math>” such that <math>\gcd(e, (p-1)\times(q-1) ) = 1</math>. That is to say, <math>e</math> and <math>(p-1)\times(q-1)</math> are relatively prime to each other. |
|||
The decryption value <math>d</math> is then found by solving |
|||
: <math>d\times e \equiv 1 \mod (p-1)\times(q-1)</math> |
|||
The security of the code is based on the secrecy of the Private Key (decryption exponent) “<math>d</math>” and the difficulty in factoring “<math>n</math>”. Research into RSA facilitated advances in factoring and a number of [http://www.rsa.com/rsalabs/node.asp?id=2092 factoring challenges]. Keys of 829 bits have been successfully factored, and NIST now recommends 2048 bit keys going forward (see [[wp:Key_size#Asymmetric_algorithm_key_lengths|Asymmetric algorithm key lengths]]). |
|||
'''Summary of the task requirements:''' |
|||
* Encrypt and Decrypt a short message or two using RSA with a demonstration key. |
|||
* Implement RSA do not call a library. |
|||
* Encode and decode the message using any reversible method of your choice (ASCII or a=1,..,z=26 are equally fine). |
|||
* Either support blocking or give an error if the message would require blocking) |
|||
* Demonstrate that your solution could support real keys by using a non-trivial key that requires large integer support (built-in or libraries). There is no need to include library code but it must be referenced unless it is built into the language. The following keys will be meet this requirement;however, they are NOT long enough to be considered secure: |
|||
:: n = 9516311845790656153499716760847001433441357 |
|||
:: e = 65537 |
|||
:: d = 5617843187844953170308463622230283376298685 |
|||
* Messages can be hard-coded into the program, there is no need for elaborate input coding. |
|||
* Demonstrate that your implementation works by showing plaintext, intermediate results, encrypted text, and decrypted text. |
|||
{{alertbox|#ffff70|'''<big>Warning</big>'''<br/>Rosetta Code is '''not''' a place you should rely on for examples of code in critical roles, including security.<br/>Cryptographic routines should be validated before being used.<br/>For a discussion of limitations and please refer to [[Talk:RSA_code#Difference_from_practical_cryptographical_version]].}} |
|||
=={{header|11l}}== |
|||
{{trans|D}} |
|||
<syntaxhighlight lang="11l">V n = BigInt(‘9516311845790656153499716760847001433441357’) |
|||
V e = BigInt(65537) |
|||
V d = BigInt(‘5617843187844953170308463622230283376298685’) |
|||
V txt = ‘Rosetta Code’ |
|||
print(‘Plain text: ’txt) |
|||
V txtN = txt.reduce(BigInt(0), (a, b) -> a * 256 + b.code) |
|||
print(‘Plain text as a number: ’txtN) |
|||
V enc = pow(txtN, e, n) |
|||
print(‘Encoded: ’enc) |
|||
V dec = pow(enc, d, n) |
|||
print(‘Decoded: ’dec) |
|||
V decTxt = ‘’ |
|||
L dec != 0 |
|||
decTxt ‘’= Char(code' dec % 256) |
|||
dec I/= 256 |
|||
print(‘Decoded number as text: ’reversed(decTxt))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Plain text: Rosetta Code |
|||
Plain text as a number: 25512506514985639724585018469 |
|||
Encoded: 916709442744356653386978770799029131264344 |
|||
Decoded: 25512506514985639724585018469 |
|||
Decoded number as text: Rosetta Code |
|||
</pre> |
|||
=={{header|Ada}}== |
|||
The code below uses a thik and a thin binding of gmp. |
|||
<syntaxhighlight lang="ada"> |
|||
WITH GMP, GMP.Integers, Ada.Text_IO, GMP.Integers.Aliased_Internal_Value, Interfaces.C; |
|||
USE GMP, Gmp.Integers, Ada.Text_IO, Interfaces.C; |
|||
PROCEDURE Main IS |
|||
FUNCTION "+" (U : Unbounded_Integer) RETURN Mpz_T IS (Aliased_Internal_Value (U)); |
|||
FUNCTION "+" (S : String) RETURN Unbounded_Integer IS (To_Unbounded_Integer (S)); |
|||
FUNCTION Image_Cleared (M : Mpz_T) RETURN String IS (Image (To_Unbounded_Integer (M))); |
|||
N : Unbounded_Integer := +"9516311845790656153499716760847001433441357"; |
|||
E : Unbounded_Integer := +"65537"; |
|||
D : Unbounded_Integer := +"5617843187844953170308463622230283376298685"; |
|||
Plain_Text : CONSTANT String := "Rosetta Code"; |
|||
M, M_C, M_D : Mpz_T; |
|||
-- We import two C functions from the GMP library which are not in the specs of the gmp package |
|||
PROCEDURE Mpz_Import |
|||
(Rop : Mpz_T; Count : Size_T; Order : Int; Size : Size_T; Endian : Int; |
|||
Nails : Size_T; Op : Char_Array); |
|||
PRAGMA Import (C, Mpz_Import, "__gmpz_import"); |
|||
PROCEDURE Mpz_Export |
|||
(Rop : OUT Char_Array; Count : ACCESS Size_T; Order : Int; Size : Size_T; |
|||
Endian : Int; Nails : Size_T; Op : Mpz_T); |
|||
PRAGMA Import (C, Mpz_Export, "__gmpz_export"); |
|||
BEGIN |
|||
Mpz_Init (M); |
|||
Mpz_Init (M_C); |
|||
Mpz_Init (M_D); |
|||
Mpz_Import (M, Plain_Text'Length + 1, 1, 1, 0, 0, To_C (Plain_Text)); |
|||
Mpz_Powm (M_C, M, +E, +N); |
|||
Mpz_Powm (M_D, M_C, +D, +N); |
|||
Put_Line ("Encoded plain text: " & Image_Cleared (M)); |
|||
DECLARE Decrypted : Char_Array (1 .. Mpz_Sizeinbase (M_C, 256)); |
|||
BEGIN |
|||
Put_Line ("Encryption of this encoding: " & Image_Cleared (M_C)); |
|||
Mpz_Export (Decrypted, NULL, 1, 1, 0, 0, M_D); |
|||
Put_Line ("Decryption of the encoding: " & Image_Cleared (M_D)); |
|||
Put_Line ("Final decryption: " & To_Ada (Decrypted)); |
|||
END; |
|||
END Main; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Encoded plain text: 6531201667836323769493764728064 |
|||
Encryption of this encoding: 8527003485686414372697775926080309566820293 |
|||
Decryption of the encoding: 6531201667836323769493764728064 |
|||
Final decryption: Rosetta Code |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
|||
The code below uses Algol 68 Genie which provides arbitrary precision arithmetic for LONG LONG modes. |
|||
<syntaxhighlight lang="algol68"> |
|||
COMMENT |
|||
First cut. Doesn't yet do blocking and deblocking. Also, as |
|||
encryption and decryption are identical operations but for the |
|||
reciprocal exponents used, only one has been implemented below. |
|||
A later release will address these issues. |
|||
COMMENT |
|||
BEGIN |
|||
PR precision=1000 PR |
|||
MODE LLI = LONG LONG INT; CO For brevity CO |
|||
PROC mod power = (LLI base, exponent, modulus) LLI : |
|||
BEGIN |
|||
LLI result := 1, b := base, e := exponent; |
|||
IF exponent < 0 |
|||
THEN |
|||
put (stand error, (("Negative exponent", exponent, newline))) |
|||
ELSE |
|||
WHILE e > 0 |
|||
DO |
|||
(ODD e | result := (result * b) MOD modulus); |
|||
e OVERAB 2; b := (b * b) MOD modulus |
|||
OD |
|||
FI; |
|||
result |
|||
END; |
|||
PROC modular inverse = (LLI a, m) LLI : |
|||
BEGIN |
|||
PROC extended gcd = (LLI x, y) []LLI : |
|||
BEGIN |
|||
LLI v := 1, a := 1, u := 0, b := 0, g := x, w := y; |
|||
WHILE w>0 |
|||
DO |
|||
LLI q := g % w, t := a - q * u; |
|||
a := u; u := t; |
|||
t := b - q * v; |
|||
b := v; v := t; |
|||
t := g - q * w; |
|||
g := w; w := t |
|||
OD; |
|||
a PLUSAB (a < 0 | u | 0); |
|||
(a, b, g) |
|||
END; |
|||
[] LLI egcd = extended gcd (a, m); |
|||
(egcd[3] > 1 | 0 | egcd[1] MOD m) |
|||
END; |
|||
PROC number to string = (LLI number) STRING : |
|||
BEGIN |
|||
[] CHAR map = (blank + "ABCDEFGHIJKLMNOPQRSTUVWXYZ")[@0]; |
|||
LLI local number := number; |
|||
INT length := SHORTEN SHORTEN ENTIER long long log(number) + 1; |
|||
(ODD length | length PLUSAB 1); |
|||
[length % 2] CHAR text; |
|||
FOR i FROM length % 2 BY -1 TO 1 |
|||
DO |
|||
INT index = SHORTEN SHORTEN (local number MOD 100); |
|||
text[i] := (index > 26 | "?" | map[index]); |
|||
local number := local number % 100 |
|||
OD; |
|||
text |
|||
END; |
|||
CO The parameters of a particular RSA cryptosystem CO |
|||
LLI p = 3490529510847650949147849619903898133417764638493387843990820577; |
|||
LLI q = 32769132993266709549961988190834461413177642967992942539798288533; |
|||
LLI n = p * q; |
|||
LLI phi n = (p-1) * (q-1); |
|||
LLI e = 9007; |
|||
LLI d = modular inverse (e, phi n); |
|||
CO A ciphertext CO |
|||
LLI cipher text = 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154; |
|||
CO Print out the corresponding plain text CO |
|||
print (number to string (mod power (ciphertext, d, n))) |
|||
END |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE |
|||
</pre> |
|||
=={{header|C}}== |
|||
{{libheader|GMP}} |
|||
<syntaxhighlight lang="c"> |
|||
#include <stdio.h> |
|||
#include <stdlib.h> |
|||
#include <string.h> |
|||
#include <gmp.h> |
|||
int main(void) |
|||
{ |
|||
mpz_t n, d, e, pt, ct; |
|||
mpz_init(pt); |
|||
mpz_init(ct); |
|||
mpz_init_set_str(n, "9516311845790656153499716760847001433441357", 10); |
|||
mpz_init_set_str(e, "65537", 10); |
|||
mpz_init_set_str(d, "5617843187844953170308463622230283376298685", 10); |
|||
const char *plaintext = "Rossetta Code"; |
|||
mpz_import(pt, strlen(plaintext), 1, 1, 0, 0, plaintext); |
|||
if (mpz_cmp(pt, n) > 0) |
|||
abort(); |
|||
mpz_powm(ct, pt, e, n); |
|||
gmp_printf("Encoded: %Zd\n", ct); |
|||
mpz_powm(pt, ct, d, n); |
|||
gmp_printf("Decoded: %Zd\n", pt); |
|||
char buffer[64]; |
|||
mpz_export(buffer, NULL, 1, 1, 0, 0, pt); |
|||
printf("As String: %s\n", buffer); |
|||
mpz_clears(pt, ct, n, e, d, NULL); |
|||
return 0; |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Encoded: 5278143020249600501803788468419399384934220 |
|||
Decoded: 6531201733672758787904906421349 |
|||
As String: Rossetta Code |
|||
</pre> |
|||
=={{header|C sharp|C#}}== |
|||
{{libheader|System.Numerics}} |
|||
<syntaxhighlight lang="csharp">using System; |
|||
using System.Numerics; |
|||
using System.Text; |
|||
class Program |
|||
{ |
|||
static void Main(string[] args) |
|||
{ |
|||
BigInteger n = BigInteger.Parse("9516311845790656153499716760847001433441357"); |
|||
BigInteger e = 65537; |
|||
BigInteger d = BigInteger.Parse("5617843187844953170308463622230283376298685"); |
|||
const string plaintextstring = "Hello, Rosetta!"; |
|||
byte[] plaintext = ASCIIEncoding.ASCII.GetBytes(plaintextstring); |
|||
BigInteger pt = new BigInteger(plaintext); |
|||
if (pt > n) |
|||
throw new Exception(); |
|||
BigInteger ct = BigInteger.ModPow(pt, e, n); |
|||
Console.WriteLine("Encoded: " + ct); |
|||
BigInteger dc = BigInteger.ModPow(ct, d, n); |
|||
Console.WriteLine("Decoded: " + dc); |
|||
string decoded = ASCIIEncoding.ASCII.GetString(dc.ToByteArray()); |
|||
Console.WriteLine("As ASCII: " + decoded); |
|||
} |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Encoded: 8545729659809274764853392532557102329563535 |
|||
Decoded: 173322416552962951144796590453843272 |
|||
As ASCII: Hello, Rosetta!</pre> |
|||
=={{header|Common Lisp}}== |
|||
In this example, the functions encode-string and decode-string are responsible for converting the string to an integer (which can be encoded) and back. They are not very important to the RSA algorithm, which happens in encode-rsa, decode-rsa, and mod-exp. |
|||
The string is encoded as follows: each character is converted into 2 digits based on ASCII value (subtracting 32, so that SPACE=00, and so on.) To decode we simply read every 2 digits from the given integer in order, adding 32 and converting back into characters. |
|||
<syntaxhighlight lang="lisp">(defparameter *n* 9516311845790656153499716760847001433441357) |
|||
(defparameter *e* 65537) |
|||
(defparameter *d* 5617843187844953170308463622230283376298685) |
|||
;; magic |
|||
(defun encode-string (message) |
|||
(parse-integer (reduce #'(lambda (x y) (concatenate 'string x y)) |
|||
(loop for c across message collect (format nil "~2,'0d" (- (char-code c) 32)))))) |
|||
;; sorcery |
|||
(defun decode-string (message) (coerce (loop for (a b) on |
|||
(loop for char across (write-to-string message) collect char) |
|||
by #'cddr collect (code-char (+ (parse-integer (coerce (list a b) 'string)) 32))) 'string)) |
|||
;; ACTUAL RSA ALGORITHM STARTS HERE ;; |
|||
;; fast modular exponentiation: runs in O(log exponent) |
|||
;; acc is initially 1 and contains the result by the end |
|||
(defun mod-exp (base exponent modulus acc) |
|||
(if (= exponent 0) acc |
|||
(mod-exp (mod (* base base) modulus) (ash exponent -1) modulus |
|||
(if (= (mod exponent 2) 1) (mod (* acc base) modulus) acc)))) |
|||
;; to encode a message, we first convert it to its integer form. |
|||
;; then, we raise it to the *e* power, modulo *n* |
|||
(defun encode-rsa (message) |
|||
(mod-exp (encode-string message) *e* *n* 1)) |
|||
;; to decode a message, we raise it to *d* power, modulo *n* |
|||
;; and then convert it back into a string |
|||
(defun decode-rsa (message) |
|||
(decode-string (mod-exp message *d* *n* 1))) |
|||
</syntaxhighlight> |
|||
Interpreter output (the star * represents the interpreter prompt): |
|||
<pre> |
|||
* (load "rsa.lisp") |
|||
T |
|||
* (encode-rsa "Rosetta Code") |
|||
4330737636866106722999010287941987299297557 |
|||
* (decode-rsa 4330737636866106722999010287941987299297557) |
|||
"Rosetta Code" |
|||
</pre> |
|||
=={{header|D}}== |
|||
This used the D module of the Modular Exponentiation Task. |
|||
{{trans|Go}} |
|||
<syntaxhighlight lang="d">void main() { |
|||
import std.stdio, std.bigint, std.algorithm, std.string, std.range, |
|||
modular_exponentiation; |
|||
immutable txt = "Rosetta Code"; |
|||
writeln("Plain text: ", txt); |
|||
// 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. |
|||
immutable BigInt n = "2463574872878749457479".BigInt * |
|||
"3862806018422572001483".BigInt; |
|||
immutable BigInt e = 2 ^^ 16 + 1; |
|||
immutable BigInt d = "5617843187844953170308463622230283376298685"; |
|||
// Convert plain text to a number. |
|||
immutable txtN = reduce!q{ (a << 8) | uint(b) }(0.BigInt, txt); |
|||
if (txtN >= n) |
|||
return writeln("Plain text message too long."); |
|||
writeln("Plain text as a number: ", txtN); |
|||
// Encode a single number. |
|||
immutable enc = txtN.powMod(e, n); |
|||
writeln("Encoded: ", enc); |
|||
// Decode a single number. |
|||
auto dec = enc.powMod(d, n); |
|||
writeln("Decoded: ", dec); |
|||
// Convert number to text. |
|||
char[] decTxt; |
|||
for (; dec; dec >>= 8) |
|||
decTxt ~= (dec & 0xff).toInt; |
|||
writeln("Decoded number as text: ", decTxt.retro); |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Plain text: Rosetta Code |
|||
Plain text as a number: 25512506514985639724585018469 |
|||
Encoded: 916709442744356653386978770799029131264344 |
|||
Decoded: 25512506514985639724585018469 |
|||
Decoded number as text: Rosetta Code</pre> |
|||
=={{header|Delphi}}== |
|||
{{libheader| System.SysUtils}} |
|||
{{libheader| Velthuis.BigIntegers}} |
|||
{{Trans|Go}} |
|||
Thanks for Rudy Velthuis, BigIntegers library |
|||
<syntaxhighlight lang="delphi"> |
|||
program RSA_code; |
|||
{$APPTYPE CONSOLE} |
|||
uses |
|||
System.SysUtils, |
|||
Velthuis.BigIntegers; |
|||
type |
|||
TRSA = record |
|||
private |
|||
n, e, d: BigInteger; |
|||
class function PlainTextAsNumber(data: AnsiString): BigInteger; static; |
|||
class function NumberAsPlainText(Num: BigInteger): AnsiString; static; |
|||
public |
|||
constructor Create(n, e, d: string); |
|||
function Encode(data: AnsiString): string; |
|||
function Decode(code: string): AnsiString; |
|||
end; |
|||
function EncodeRSA(data: AnsiString): string; |
|||
var |
|||
n, e, d, bb, ptn, etn, dtn: BigInteger; |
|||
begin |
|||
// 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 := '9516311845790656153499716760847001433441357'; |
|||
e := '65537'; |
|||
d := '5617843187844953170308463622230283376298685'; |
|||
for var c in data do |
|||
begin |
|||
bb := ord(c); |
|||
ptn := (ptn shl 8) or bb; |
|||
end; |
|||
if BigInteger.Compare(ptn, n) >= 0 then |
|||
begin |
|||
Writeln('Plain text message too long'); |
|||
exit; |
|||
end; |
|||
writeln('Plain text as a number:', ptn.ToString); |
|||
writeln(ptn.ToString); |
|||
// encode a single number |
|||
etn := BigInteger.ModPow(ptn, e, n); |
|||
Writeln('Encoded: ', etn.ToString); |
|||
// decode a single number |
|||
dtn := BigInteger.ModPow(etn, d, n); |
|||
Writeln('Decoded: ', dtn.ToString); |
|||
// convert number to text |
|||
var db: AnsiString; |
|||
var bff: BigInteger := $FF; |
|||
while dtn.BitLength > 0 do |
|||
begin |
|||
db := ansichar((dtn and bff).AsInteger) + db; |
|||
dtn := dtn shr 8; |
|||
end; |
|||
Write('Decoded number as text:"', db, '"'); |
|||
end; |
|||
const |
|||
pt = 'Rosetta Code'; |
|||
{ TRSA } |
|||
constructor TRSA.Create(n, e, d: string); |
|||
begin |
|||
self.n := n; |
|||
self.e := e; |
|||
self.d := d; |
|||
end; |
|||
function TRSA.Decode(code: string): AnsiString; |
|||
var |
|||
etn, dtn: BigInteger; |
|||
begin |
|||
// decode a single number |
|||
etn := code; |
|||
dtn := BigInteger.ModPow(etn, d, n); |
|||
Result := NumberAsPlainText(dtn); |
|||
end; |
|||
function TRSA.Encode(data: AnsiString): string; |
|||
var |
|||
ptn: BigInteger; |
|||
begin |
|||
ptn := PlainTextAsNumber(data); |
|||
// encode a single number |
|||
Result := BigInteger.ModPow(ptn, e, n).ToString; |
|||
end; |
|||
class function TRSA.NumberAsPlainText(Num: BigInteger): AnsiString; |
|||
var |
|||
bff: BigInteger; |
|||
begin |
|||
// convert number to text |
|||
bff := $FF; |
|||
Result := ''; |
|||
while Num.BitLength > 0 do |
|||
begin |
|||
Result := ansichar((Num and bff).AsInteger) + Result; |
|||
Num := Num shr 8; |
|||
end; |
|||
end; |
|||
class function TRSA.PlainTextAsNumber(data: AnsiString): BigInteger; |
|||
var |
|||
c: AnsiChar; |
|||
bb, n: BigInteger; |
|||
begin |
|||
Result := 0; |
|||
n := '9516311845790656153499716760847001433441357'; |
|||
for c in data do |
|||
begin |
|||
bb := ord(c); |
|||
Result := (Result shl 8) or bb; |
|||
end; |
|||
if BigInteger.Compare(Result, n) >= 0 then |
|||
raise Exception.Create('Plain text message too long'); |
|||
end; |
|||
var |
|||
RSA: TRSA; |
|||
Encoded: string; |
|||
const |
|||
n = '9516311845790656153499716760847001433441357'; |
|||
e = '65537'; |
|||
d = '5617843187844953170308463622230283376298685'; |
|||
TEST_WORD = 'Rosetta Code'; |
|||
begin |
|||
RSA := TRSA.Create(n, e, d); |
|||
Encoded := RSA.Encode(TEST_WORD); |
|||
writeln('Plain text: ', TEST_WORD); |
|||
writeln('Encoded: ', Encoded); |
|||
writeln('Decoded: ', RSA.Decode(Encoded)); |
|||
Readln; |
|||
end.</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Plain text: Rosetta Code |
|||
Encoded: 916709442744356653386978770799029131264344 |
|||
Decoded: Rosetta Code</pre> |
|||
=={{header|Erlang}}== |
|||
Solution split into 2 modules, the mod module does the modulo aritmetic as per separate Rosetta Code entry. |
|||
<syntaxhighlight lang="erlang"> |
|||
%%% @author Tony Wallace <tony@tony.gen.nz> |
|||
%%% @doc |
|||
%%% For details of the algorithms used see |
|||
%%% https://en.wikipedia.org/wiki/Modular_exponentiation |
|||
%%% @end |
|||
%%% Created : 21 Jul 2021 by Tony Wallace <tony@resurrection> |
|||
-module mod. |
|||
-export [mod_mult/3,mod_exp/3,binary_exp/2,test/0]. |
|||
mod_mult(I1,I2,Mod) when |
|||
I1 > Mod, |
|||
is_integer(I1), is_integer(I2), is_integer(Mod) -> |
|||
mod_mult(I1 rem Mod,I2,Mod); |
|||
mod_mult(I1,I2,Mod) when |
|||
I2 > Mod, |
|||
is_integer(I1), is_integer(I2), is_integer(Mod) -> |
|||
mod_mult(I1,I2 rem Mod,Mod); |
|||
mod_mult(I1,I2,Mod) when |
|||
is_integer(I1), is_integer(I2), is_integer(Mod) -> |
|||
(I1 * I2) rem Mod. |
|||
mod_exp(Base,Exp,Mod) when |
|||
is_integer(Base), |
|||
is_integer(Exp), |
|||
is_integer(Mod), |
|||
Base > 0, |
|||
Exp > 0, |
|||
Mod > 0 -> |
|||
binary_exp_mod(Base,Exp,Mod); |
|||
mod_exp(_,0,_) -> 1. |
|||
binary_exp(Base,Exponent) when |
|||
is_integer(Base), |
|||
is_integer(Exponent), |
|||
Base > 0, |
|||
Exponent > 0 -> |
|||
binary_exp(Base,Exponent,1); |
|||
binary_exp(_,0) -> |
|||
1. |
|||
binary_exp(_,0,Result) -> |
|||
Result; |
|||
binary_exp(Base,Exponent,Acc) -> |
|||
binary_exp(Base*Base,Exponent bsr 1,Acc * exp_factor(Base,Exponent)). |
|||
binary_exp_mod(Base,Exponent,Mod) -> |
|||
binary_exp_mod(Base rem Mod,Exponent,Mod,1). |
|||
binary_exp_mod(_,0,_,Result) -> |
|||
Result; |
|||
binary_exp_mod(Base,Exponent,Mod,Acc) -> |
|||
binary_exp_mod((Base*Base) rem Mod, |
|||
Exponent bsr 1,Mod,(Acc * exp_factor(Base,Exponent))rem Mod). |
|||
exp_factor(_,0) -> |
|||
1; |
|||
exp_factor(Base,1) -> |
|||
Base; |
|||
exp_factor(Base,Exponent) -> |
|||
exp_factor(Base,Exponent band 1). |
|||
test() -> |
|||
445 = mod_exp(4,13,497), |
|||
%% Rosetta code example: |
|||
R = 1527229998585248450016808958343740453059 = |
|||
mod_exp(2988348162058574136915891421498819466320163312926952423791023078876139, |
|||
2351399303373464486466122544523690094744975233415544072992656881240319, |
|||
binary_exp(10,40)), |
|||
R. |
|||
%%%------------------------------------------------------------------- |
|||
%%% @author Tony Wallace <tony@tony.gen.nz> |
|||
%%% @doc |
|||
%%% Blocking not implemented. Runtime exception if message too long |
|||
%%% Not a practical issue as RSA usually limited to symmetric key exchange |
|||
%%% However as a key exchange tool no advantage in compressing plaintext |
|||
%%% so that is not done either. |
|||
%%% @end |
|||
%%% Created : 24 Jul 2021 by Tony Wallace <tony@resurrection> |
|||
%%%------------------------------------------------------------------- |
|||
-module rsa. |
|||
-export([key_gen/2,encrypt/2,decrypt/2,test/0]). |
|||
-type key() :: {integer(),integer()}. |
|||
key_gen({N,D},E) -> |
|||
{{E,N},{D,N}}. |
|||
-spec encrypt(key(),integer()) -> integer(). |
|||
encrypt({E,N},MessageInt) |
|||
when MessageInt < N -> |
|||
mod:mod_exp(MessageInt,E,N). |
|||
-spec decrypt(key(),integer()) -> integer(). |
|||
decrypt({D,N},Message) -> |
|||
mod:mod_exp(Message,D,N). |
|||
test() -> |
|||
PlainText=10722935, |
|||
N = 9516311845790656153499716760847001433441357, |
|||
E = 65537, |
|||
D = 5617843187844953170308463622230283376298685, |
|||
{PublicKey,PrivateKey} = key_gen({N,D},E), |
|||
PlainText =:= decrypt(PrivateKey, |
|||
encrypt(PublicKey,PlainText)). |
|||
</syntaxhighlight> |
|||
Running test: |
|||
8> rsa:test(). |
|||
rsa:test(). |
|||
true |
|||
9> |
|||
=={{header|F Sharp|F#}}== |
|||
<syntaxhighlight lang="fsharp"> |
|||
//Nigel Galloway February 12th., 2018 |
|||
let RSA n g l = bigint.ModPow(l,n,g) |
|||
let encrypt = RSA 65537I 9516311845790656153499716760847001433441357I |
|||
let m_in = System.Text.Encoding.ASCII.GetBytes "The magic words are SQUEAMISH OSSIFRAGE"|>Array.chunkBySize 16|>Array.map(Array.fold(fun n g ->(n*256I)+(bigint(int g))) 0I) |
|||
let n = Array.map encrypt m_in |
|||
let decrypt = RSA 5617843187844953170308463622230283376298685I 9516311845790656153499716760847001433441357I |
|||
let g = Array.map decrypt n |
|||
let m_out = Array.collect(fun n->Array.unfold(fun n->if n>0I then Some(byte(int (n%256I)),n/256I) else None) n|>Array.rev) g|>System.Text.Encoding.ASCII.GetString |
|||
printfn "'The magic words are SQUEAMISH OSSIFRAGE' as numbers -> %A\nEncrypted -> %A\nDecrypted -> %A\nAs text -> %A" m_in n g m_out |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
'The magic words are SQUEAMISH OSSIFRAGE' as numbers -> [|112197201611743344895286521511035564832; 129529088517466560781735691575334293331; 23442989443532613|] |
|||
Encrypted -> [|3493129515654757560886946157927565680562316; 5582490186309277335090560762784439391588703; 8700785834706594190338047528968122486721264|] |
|||
Decrypted -> [|112197201611743344895286521511035564832; 129529088517466560781735691575334293331; 23442989443532613|] |
|||
As text -> "The magic words are SQUEAMISH OSSIFRAGE" |
|||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
{{trans|C}} |
|||
<syntaxhighlight lang="freebasic">' version 17-01-2017 |
|||
' compile with: fbc -s console |
|||
#Include Once "gmp.bi" |
|||
Dim As Mpz_ptr e, d, n, pt, ct |
|||
e = Allocate(Len(__mpz_struct)) |
|||
d = Allocate(Len(__mpz_struct)) |
|||
n = Allocate(Len(__mpz_struct)) |
|||
pt = Allocate(Len(__mpz_struct)) : mpz_init(pt) |
|||
ct = Allocate(Len(__mpz_struct)) : mpz_init(ct) |
|||
mpz_init_set_str(e, "65537", 10) |
|||
mpz_init_set_str(d, "5617843187844953170308463622230283376298685", 10) |
|||
mpz_init_set_str(n, "9516311845790656153499716760847001433441357", 10) |
|||
Dim As ZString Ptr plaintext : plaintext = Allocate(1000) |
|||
Dim As ZString Ptr text : text = Allocate(1000) |
|||
*plaintext = "Rosetta Code" |
|||
mpz_import(pt, Len(*plaintext), 1, 1, 0, 0, plaintext) |
|||
If mpz_cmp(pt, n) > 0 Then GoTo clean_up |
|||
mpz_powm(ct, pt, e, n) |
|||
gmp_printf(!" Encoded: %Zd\n", ct) |
|||
mpz_powm(pt, ct, d, n) |
|||
gmp_printf(!" Decoded: %Zd\n", pt) |
|||
mpz_export(text, NULL, 1, 1, 0, 0, pt) |
|||
Print "As string: "; *text |
|||
clean_up: |
|||
DeAllocate(plaintext) : DeAllocate(text) |
|||
mpz_clear(e) : mpz_clear(d) : mpz_clear(n) |
|||
mpz_clear(pt) : mpz_clear(ct) |
|||
' empty keyboard buffer |
|||
While Inkey <> "" : Wend |
|||
Print : Print "hit any key to end program" |
|||
Sleep |
|||
End</syntaxhighlight> |
|||
{{out}} |
|||
<pre> Encoded: 916709442744356653386978770799029131264344 |
|||
Decoded: 25512506514985639724585018469 |
|||
As string: Rosetta Code</pre> |
|||
=={{header|Go}}== |
|||
Note: see the [https://golang.org/pkg/crypto/rsa/ crypto/rsa] package |
|||
included with Go for a full implementation. |
|||
<syntaxhighlight lang="go">package main |
|||
import ( |
|||
"fmt" |
|||
"math/big" |
|||
) |
|||
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))) |
|||
} |
|||
if ptn.Cmp(&n) >= 0 { |
|||
fmt.Println("Plain text message too long") |
|||
return |
|||
} |
|||
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:])) |
|||
}</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
Plain text: Rosetta Code |
|||
Plain text as a number: 25512506514985639724585018469 |
|||
Encoded: 916709442744356653386978770799029131264344 |
|||
Decoded: 25512506514985639724585018469 |
|||
Decoded number as text: Rosetta Code |
|||
</pre> |
|||
=={{header|Haskell}}== |
|||
<syntaxhighlight lang="haskell">module RSAMaker |
|||
where |
|||
import Data.Char ( chr ) |
|||
encode :: String -> [Integer] |
|||
encode s = map (toInteger . fromEnum ) s |
|||
rsa_encode :: Integer -> Integer -> [Integer] -> [Integer] |
|||
rsa_encode n e numbers = map (\num -> mod ( num ^ e ) n ) numbers |
|||
rsa_decode :: Integer -> Integer -> [Integer] -> [Integer] |
|||
rsa_decode d n ciphers = map (\c -> mod ( c ^ d ) n ) ciphers |
|||
decode :: [Integer] -> String |
|||
decode encoded = map ( chr . fromInteger ) encoded |
|||
divisors :: Integer -> [Integer] |
|||
divisors n = [m | m <- [1..n] , mod n m == 0 ] |
|||
isPrime :: Integer -> Bool |
|||
isPrime n = divisors n == [1,n] |
|||
totient :: Integer -> Integer -> Integer |
|||
totient prime1 prime2 = (prime1 - 1 ) * ( prime2 - 1 ) |
|||
myE :: Integer -> Integer |
|||
myE tot = head [n | n <- [2..tot - 1] , gcd n tot == 1] |
|||
myD :: Integer -> Integer -> Integer -> Integer |
|||
myD e n phi = head [d | d <- [1..n] , mod ( d * e ) phi == 1] |
|||
main = do |
|||
putStrLn "Enter a test text!" |
|||
text <- getLine |
|||
let primes = take 90 $ filter isPrime [1..] |
|||
p1 = last primes |
|||
p2 = last $ init primes |
|||
tot = totient p1 p2 |
|||
e = myE tot |
|||
n = p1 * p2 |
|||
rsa_encoded = rsa_encode n e $ encode text |
|||
d = myD e n tot |
|||
encrypted = concatMap show rsa_encoded |
|||
decrypted = decode $ rsa_decode d n rsa_encoded |
|||
putStrLn ("Encrypted: " ++ encrypted ) |
|||
putStrLn ("And now decrypted: " ++ decrypted )</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Enter a test text! |
|||
Rosettacode |
|||
Encrypted: 65646265111107071564791028551028551458331139502651145035156479 |
|||
And now decrypted: Rosettacode |
|||
</pre> |
|||
=={{header|Icon}} and {{header|Unicon}}== |
|||
Please read talk pages. |
|||
<syntaxhighlight lang="icon">procedure main() # rsa demonstration |
|||
n := 9516311845790656153499716760847001433441357 |
|||
e := 65537 |
|||
d := 5617843187844953170308463622230283376298685 |
|||
b := 2^integer(log(n,2)) # for blocking |
|||
write("RSA Demo using\n n = ",n,"\n e = ",e,"\n d = ",d,"\n b = ",b) |
|||
every m := !["Rosetta Code", "Hello Word!", |
|||
"This message is too long.", repl("x",*decode(n+1))] do { |
|||
write("\nMessage = ",image(m)) |
|||
write( "Encoded = ",m := encode(m)) |
|||
if m := rsa(m,e,n) then { # unblocked |
|||
write( "Encrypt = ",m) |
|||
write( "Decrypt = ",m := rsa(m,d,n)) |
|||
} |
|||
else { # blocked |
|||
every put(C := [], rsa(!block(m,b),e,n)) |
|||
writes("Encrypt = ") ; every writes(!C," ") ; write() |
|||
every put(P := [], rsa(!C,d,n)) |
|||
writes("Decrypt = ") ; every writes(!P," ") ; write() |
|||
write("Unblocked = ",m := unblock(P,b)) |
|||
} |
|||
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 |
|||
procedure block(m,b) # break lg int into blocks of size b |
|||
M := [] |
|||
while push(M, x := (0 < m) % b) do |
|||
m /:= b |
|||
return M |
|||
end |
|||
procedure unblock(M,b) # reassemble blocks of size b into lg int |
|||
every (m := 0) := !M + b * m |
|||
return m |
|||
end</syntaxhighlight> |
|||
Output: |
|||
<pre>RSA Demo using |
|||
n = 9516311845790656153499716760847001433441357 |
|||
e = 65537 |
|||
d = 5617843187844953170308463622230283376298685 |
|||
b = 5575186299632655785383929568162090376495104 |
|||
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 = "This message is too long." |
|||
Encoded = 529836718428469753460978059376661024804668788418205881100078 |
|||
Encrypt = 3376966937987363040878203966915676619521252 7002174816151673360605669161609885530980579 |
|||
Decrypt = 95034800624219541 4481988526688939374478063610382714873472814 |
|||
Unblocked = 529836718428469753460978059376661024804668788418205881100078 |
|||
Decoded = "This message is too long." |
|||
Message = "xxxxxxxxxxxxxxxxxx" |
|||
Encoded = 10494468328720293243075632128305111296931960 |
|||
Encrypt = 1 829820657892505002815717051746917810425013 |
|||
Decrypt = 1 4919282029087637457691702560143020920436856 |
|||
Unblocked = 10494468328720293243075632128305111296931960 |
|||
Decoded = "xxxxxxxxxxxxxxxxxx"</pre> |
|||
For more information about RSA code: [[wp:RSA|Wikipedia: RSA code]] |
|||
=={{header|J}}== |
=={{header|J}}== |
||
Note, for an implementation with blocking (and a much smaller key) see [http://rosettacode.org/mw/index.php?title=RSA_code&oldid=103802] |
|||
<lang j>NB. keys |
|||
N=: 2537x |
|||
E=: 13x |
|||
D=: 937x |
|||
<syntaxhighlight lang="j"> N=: 9516311845790656153499716760847001433441357x |
|||
NB. blocks |
|||
E=: 65537x |
|||
letters=: 'abcdefghijklmnopqrstuvwxyz,.!? ' |
|||
D=: 5617843187844953170308463622230283376298685x |
|||
base=: 1+#letters |
|||
blocksize=: base <.@^. N |
|||
] text=: 'Rosetta Code' |
|||
pad=: base ?@#~ blocksize | -@# |
|||
Rosetta Code |
|||
txt2num=: ((-blocksize) base&#.\ 1x + letters&i. , pad) :.num2txt |
|||
] num=: 256x #. a.i.text |
|||
num2txt=: ((' ',letters) {~ ,@:#:~&(blocksize#base) ) :.txt2num |
|||
25512506514985639724585018469 |
|||
num >: N NB. check if blocking is necessary (0 means no) |
|||
0 |
|||
] enc=: N&|@^&E num |
|||
916709442744356653386978770799029131264344 |
|||
] dec=: N&|@^&D enc |
|||
25512506514985639724585018469 |
|||
] final=: a. {~ 256x #.inv dec |
|||
Rosetta Code</syntaxhighlight> |
|||
Note: as indicated at http://www.jsoftware.com/help/dictionary/special.htm, <code>N&|@^</code> does not bother with creating the exponential intermediate result. |
|||
NB. RSA algorithm |
|||
cypher=: N&|@^ |
|||
encrypt=: cypher&E@txt2num |
|||
decrypt=: num2txt@:cypher&D</lang> |
|||
=={{header|Java}}== |
|||
Example use: |
|||
<syntaxhighlight lang="java"> |
|||
<lang j> txt2num 'hi there' |
|||
public static void main(String[] args) { |
|||
265 1012 261 581 |
|||
/* |
|||
encrypt 'hi there' |
|||
This is probably not the best method...or even the most optimized way...however it works since n and d are too big to be ints or longs |
|||
695 153 2377 260 |
|||
This was also only tested with 'Rosetta Code' and 'Hello World' |
|||
decrypt 695 153 2377 260 |
|||
It's also pretty limited on plainText size (anything bigger than the above will fail) |
|||
hi there</lang> |
|||
*/ |
|||
BigInteger n = new BigInteger("9516311845790656153499716760847001433441357"); |
|||
BigInteger e = new BigInteger("65537"); |
|||
BigInteger d = new BigInteger("5617843187844953170308463622230283376298685"); |
|||
Charset c = Charsets.UTF_8; |
|||
String plainText = "Rosetta Code"; |
|||
System.out.println("PlainText : " + plainText); |
|||
byte[] bytes = plainText.getBytes(); |
|||
BigInteger plainNum = new BigInteger(bytes); |
|||
System.out.println("As number : " + plainNum); |
|||
BigInteger Bytes = new BigInteger(bytes); |
|||
if (Bytes.compareTo(n) == 1) { |
|||
System.out.println("Plaintext is too long"); |
|||
return; |
|||
} |
|||
BigInteger enc = plainNum.modPow(e, n); |
|||
System.out.println("Encoded: " + enc); |
|||
BigInteger dec = enc.modPow(d, n); |
|||
System.out.println("Decoded: " + dec); |
|||
String decText = new String(dec.toByteArray(), c); |
|||
System.out.println("As text: " + decText); |
|||
} |
|||
</syntaxhighlight> |
|||
===Alternative solution - convert to byte array then to BigInteger: === |
|||
<syntaxhighlight lang="java"> |
|||
import java.math.BigInteger; |
|||
import java.util.Random; |
|||
public class rsaCode { |
|||
public static void main(String[]args){ |
|||
//Size of primes |
|||
int BIT_LENGTH = 4096; |
|||
Random rand = new Random(); |
|||
//Generate primes and other necessary values |
|||
BigInteger p = BigInteger.probablePrime(BIT_LENGTH / 2, rand); |
|||
BigInteger q = BigInteger.probablePrime(BIT_LENGTH / 2, rand); |
|||
BigInteger n = p.multiply(q); |
|||
BigInteger phi = p.subtract(BigInteger.valueOf(1)).multiply(q.subtract(BigInteger.valueOf(1))); |
|||
BigInteger e; |
|||
BigInteger d; |
|||
do { |
|||
e = new BigInteger(phi.bitLength(), rand); |
|||
} while (e.compareTo(BigInteger.valueOf(1)) <= 0 || e.compareTo(phi) >= 0 || !e.gcd(phi).equals(BigInteger.valueOf(1))); |
|||
d = e.modInverse(phi); |
|||
//Convert message to byte array and then to a BigInteger |
|||
BigInteger message = new BigInteger("Hello World! - From Rosetta Code".getBytes()); |
|||
BigInteger cipherText = message.modPow(e, n); |
|||
BigInteger decryptedText = cipherText.modPow(d, n); |
|||
System.out.println("Message: " + message); |
|||
System.out.println("Prime 1: " + p); |
|||
System.out.println("Prime 2: " + q); |
|||
System.out.println("Phi p1 * p2: " + phi); |
|||
System.out.println("p1 * p2: " + n); |
|||
System.out.println("Public key: " + e); |
|||
System.out.println("Private key: " + d); |
|||
System.out.println("Ciphertext: " + cipherText); |
|||
System.out.println("Decrypted message(number form): " + decryptedText); |
|||
//Convert BigInteger to byte array then to String |
|||
System.out.println("Decrypted message(string): " + new String(decryptedText.toByteArray())); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Message: 32745724963520459128167607565116331713761641910444445962992228853365120918629 |
|||
Prime 1: 19236082984974163990952162748173714068049389803543876908591023542434008581726901827775282361343539027357627272183474081300821830594665417249999421476471444612045376319151307819458083226682409477411524022807762467877933511178646356355356721278159329226472299570078614830307335816363768128995044913560110586093645150502887099142708810425659608200567299323058631080348801201371891024721397456687923823598994147721120698707559677560198153919129668778208924015134166710369131053236474139106999881687335966483688956493993503452781613364724067448118712996621139377805320411264206346354690147839668674568385780953439324061827 |
|||
Prime 2: 17979329033868078796981009025342087899891110883452413861085335446537232859657584956199529432436753743100057017453176958641563538906032576785591580481524960405796753482749211728790206586594224271803757384485305551705171358489679998051039658612346599741622638134691446099105450988669667758655426868708523266671158484337114750111466361420411180131539156350206088712722069263680478398363920580976741655559629459204726096055804150577131670026585406567505359058210528861172448235138919989250928848721850118962177309953951127503325970279819172102106621073790956566530104217789478786634899278802600883073967446382373644250257 |
|||
Phi p1 * p2: 345851865309641725173652598401242058900566653910908938475312921380066114219124630361012048649340940349701681628058518630535276222954695692233147670047674008455691941733381178283159719985229687501019788350058464636500196522521346408404768715926660411771389935137989577763538670548607053837834611583177259789432946335846775973340201166384784256821490809726897985505537384164828673170953111807028144501567927080933277305734847328999516054393161305269105612852357562678721346577533872335946654435942111678921979428611842390495534195723208415846942969477148117377158823876687230703157218761840307200229212313941422321195051355226377851222163854147510935258095666300221082823130614374400292194084084333352100386386600651725502133645428505729406848959785973133150969119775159790464605612595258587741654065352840099419921194642121733262659814580729725479879031162109276830902575494117198577188807279359692336933181285455336126206772237317229756148090589146421446485136412385682723586947367965091078676401379642267664924847358476052429919297388821038943132363371365451994109675932621652038431036384121653367832798502022879709943736316295610602665722391298109723459179009548775436875778616030750642493163185541967992915955989097200396360327456 |
|||
p1 * p2: 345851865309641725173652598401242058900566653910908938475312921380066114219124630361012048649340940349701681628058518630535276222954695692233147670047674008455691941733381178283159719985229687501019788350058464636500196522521346408404768715926660411771389935137989577763538670548607053837834611583177259789432946335846775973340201166384784256821490809726897985505537384164828673170953111807028144501567927080933277305734847328999516054393161305269105612852357562678721346577533872335946654435942111678921979428611842390495534195723208415846942969477148117377158823876687230703157218761840307200229212313941422321195088570638396693464951787319284451060063606800908079113900290733389263435525468820136075198180380944495959817935065156769349234329286671127186560121733156195482447742397159107289902355166116733169136476049414801282242919450398051834285427541999782759870670431821968638118220066164725772820831757237604760059537040952069757997344764318267517273468518841355988306740438835556131045824464960305329590326517099659355766092152184867080462187317080527339823959005966347609972615672497047496190727232432065795389602582743555233621829974942652963009404343619187532820114040659804327626152774968610262473598342324536209328639539 |
|||
Public key: 193579940416764762032781091221143757801413904551984303885407040026321908965197971867687112770438003048686335467825121571041736775396425178706013366881005246973351188647629560663037810331045292388828497048500842585316962463760854316963245076613682542629780184301654965436793943481122744003077197338402843407520722504896640189710671321124115630104805979401188537742997889316213029383963089439143905748656345056757946693819634971714186428073990059096062771479710217863926284515341443931092854041306087536208153864059633604334787035313177701948799425284530371404018395643074910533253129726213643193854656336232925658951811658248314007700619000559672273590950586652099230800733098520827807590026231300954320448333065980082309254977488081625340716095420728271744505284703847569933308644755417715559811180764086973488668246118187715534944871349843316776293048731714297576612062481854912918664986385922123428018736434561518771685854566894264705876397229699222060976725454055036743075458563364307745597456824543609383372429743649103452964024219143956601668222718087847554469024737873441872945480724976527827721060219946775750776694792509727838512629661637130805269017888622785492890741411798087685393616016451666522802755139926311245306229041 |
|||
Private key: 219036175169203544315490853999486820834618560996816043411987210664248102884377915567272406198057873662330646577076795355640818453754512006948660586443609679011052139043660581484406998357727395227184641632029033848943507736672039637904589489626534363470520344933214278535075666039716685014892551021861132000517572948046870070641407067319704943583671179776670601874690644590228314092730047599467716558027443683253737751585758991176998516378325292822247842855150355043416320003512453741917219948896684868393696007264717697967091707113384847407621846752255898098912112528872599250195047315005253431619786863325536528182598792588704861531564144935586585480994816595663012912390628905402008731003235520424397350241617043412307761990786711273480686856614955176903059108533627807572077696388568308581773433971401736018773723311485647784158083000913638874130114372027510789163873963163280849749880619112666293979830817843596818936327354256104400652111217685523782967475741729222155996255475772715455781288940265345618022791173798222315117453828105848080873781770073614996444414329484314974671715475986173113744470587849073918357399130907446602201256421236363869748993676713228862789197394591401079130691347928057018496258825068434610372879057 |
|||
Ciphertext: 751802077965963630324549365263121640277689482825128224616526073196054301029392106215761462171255492597878612184351606323296123153021421277191908278007450520130118453205040455128556435393691729542297181525367763857641211099694558032110059874156910175402903627759175935900055257215548262301358748652386044838566618270488287858766869634274195146217020325014127218881028662056032737660265341221411932659292844178938078127559747544470249139600492686861162904399444542749100026596955221740375230453344396141534329779530430928001439479395156999496805099234924399049952788417632216512939528956109220706809364166228124854558311835437452608371779980805227059349785343399382366770619320980575920634550115026075376299109862825119723058827075167366432962208711425854647134395509013075755502864140908914499073909257771585668395445413050111450415828406012614877021632277223689796818643848597729370856433117827304201297547912764020996146635163811573223631120712910083451904964228318515972103019499763177402019351409722785807448842923761649884358555226283418059099812653679780193380193208207168410802721122329377467373427784070234188000453256581358361888268040964222190110448131244743936030485464773996914221120717918807573232494076059754978713933 |
|||
Decrypted message(number form): 32745724963520459128167607565116331713761641910444445962992228853365120918629 |
|||
Decrypted message(string): Hello World! - From Rosetta Code</pre> |
|||
=={{header|jq}}== |
|||
'''Adapted from [[#Wren|Wren]] after correcting for a bug in the decode-to-text algorithm''' as of 2023-02-07 |
|||
'''Works with gojq, the Go implementation of jq, and with fq''' |
|||
The following assumes unbounded-precision integer arithmetic. |
|||
<syntaxhighlight lang=jq> |
|||
# If $j is 0, then an error condition is raised; |
|||
# otherwise, assuming infinite-precision integer arithmetic, |
|||
# if the input and $j are integers, then the result will be an integer. |
|||
def idivide($j): (. - (. % $j)) / $j ; |
|||
# shift left |
|||
def left8: 256 * .; |
|||
# shift right |
|||
def right8: idivide(256); |
|||
def modPow($b; $e; $m): |
|||
if ($m == 1) then 0 |
|||
else {b: ($b % $m), $e, r: 1} |
|||
| until( .e <= 0 or .return; |
|||
if .b == 0 then .return = 0 |
|||
else if .e % 2 == 1 then .r = (.r * .b) % $m else . end |
|||
| .e |= idivide(2) |
|||
| .b = (.b * .b) % $m |
|||
end) |
|||
| if .return then .return else .r end |
|||
end; |
|||
# Convert the input integer to a stream of 8-bit integers, most significant first |
|||
def bytes: |
|||
def stream: |
|||
recurse(if . >= 256 then ./256|floor else empty end) | . % 256 ; |
|||
[stream] | reverse ; |
|||
# convert ASCII plain text to a number |
|||
def ptn: |
|||
reduce explode[] as $b (0; left8 + $b); |
|||
def n: 9516311845790656153499716760847001433441357; |
|||
def e: 65537; |
|||
def d: 5617843187844953170308463622230283376298685; |
|||
# encode a single number |
|||
def etn: . as $ptn | modPow($ptn; e; n); |
|||
# decode a single number |
|||
def dtn: . as $etn | modPow($etn; d; n); |
|||
def decode: |
|||
[recurse(right8 | select(.>0)) % 256] |
|||
| reverse |
|||
| implode; |
|||
def task($pt): |
|||
($pt|ptn) as $ptn |
|||
| if ($ptn >= n) then "Plain text message too long" | error else . end |
|||
| ($ptn|etn) as $etn |
|||
| ($etn|dtn) as $dtn |
|||
| ($ptn|decode) as $text |
|||
| "Plain text: : \($pt)", |
|||
"Plain text as a number : \($ptn)", |
|||
"Encoded : \($etn)", |
|||
"Decoded : \($dtn)", |
|||
"Decoded number as text : \($text)" |
|||
; |
|||
task("Rosetta Code"), |
|||
"", |
|||
task("Hello, Rosetta!!!!") |
|||
</syntaxhighlight> |
|||
'''Invocation''': gojq -nr -f rsa-code.jq |
|||
{{output}} |
|||
<pre> |
|||
Plain text: : Rosetta Code |
|||
Plain text as a number : 25512506514985639724585018469 |
|||
Encoded : 916709442744356653386978770799029131264344 |
|||
Decoded : 25512506514985639724585018469 |
|||
Decoded number as text : Rosetta Code |
|||
Plain text: : Hello, Rosetta!!!! |
|||
Plain text as a number : 6306597225792201544376884997106189304144161 |
|||
Encoded : 3763881655974029977658577646869029457590896 |
|||
Decoded : 6306597225792201544376884997106189304144161 |
|||
Decoded number as text : Hello, Rosetta!!!! |
|||
</pre> |
|||
=={{header|Julia}}== |
|||
{{works with|Julia|0.6}} |
|||
<syntaxhighlight lang="julia">function rsaencode(clearmsg::AbstractString, nmod::Integer, expub::Integer) |
|||
bytes = parse(BigInt, "0x" * bytes2hex(collect(UInt8, clearmsg))) |
|||
return powermod(bytes, expub, nmod) |
|||
end |
|||
function rsadecode(cryptmsg::Integer, nmod::Integer, dsecr::Integer) |
|||
decoded = powermod(encoded, dsecr, nmod) |
|||
return join(Char.(hex2bytes(hex(decoded)))) |
|||
end |
|||
msg = "Rosetta Code." |
|||
nmod = big"9516311845790656153499716760847001433441357" |
|||
expub = 65537 |
|||
dsecr = big"5617843187844953170308463622230283376298685" |
|||
encoded = rsaencode(msg, nmod, expub) |
|||
decoded = rsadecode(encoded, nmod, dsecr) |
|||
println("\n# $msg\n -> ENCODED: $encoded\n -> DECODED: $decoded")</syntaxhighlight> |
|||
{{out}} |
|||
<pre># Rosetta Code. |
|||
-> ENCODED: 2440331969632134446717000067136916252596373 |
|||
-> DECODED: Rosetta Code.</pre> |
|||
=={{header|Kotlin}}== |
|||
<syntaxhighlight lang="scala">// version 1.1.4-3 |
|||
import java.math.BigInteger |
|||
fun main(args: Array<String>) { |
|||
val n = BigInteger("9516311845790656153499716760847001433441357") |
|||
val e = BigInteger("65537") |
|||
val d = BigInteger("5617843187844953170308463622230283376298685") |
|||
val c = Charsets.UTF_8 |
|||
val plainText = "Rosetta Code" |
|||
println("PlainText : $plainText") |
|||
val bytes = plainText.toByteArray(c) |
|||
val plainNum = BigInteger(bytes) |
|||
println("As number : $plainNum") |
|||
if (plainNum > n) { |
|||
println("Plaintext is too long") |
|||
return |
|||
} |
|||
val enc = plainNum.modPow(e, n) |
|||
println("Encoded : $enc") |
|||
val dec = enc.modPow(d, n) |
|||
println("Decoded : $dec") |
|||
val decText = dec.toByteArray().toString(c) |
|||
println("As text : $decText") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
PlainText : Rosetta Code |
|||
As number : 25512506514985639724585018469 |
|||
Encoded : 916709442744356653386978770799029131264344 |
|||
Decoded : 25512506514985639724585018469 |
|||
As text : Rosetta Code |
|||
</pre> |
|||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
Does not support blocking. |
|||
<syntaxhighlight lang="text">toNumPlTxt[s_] := FromDigits[ToCharacterCode[s], 256]; |
|||
fromNumPlTxt[plTxt_] := FromCharacterCode[IntegerDigits[plTxt, 256]]; |
|||
enc::longmess = "Message '``' is too long for n = ``."; |
|||
enc[n_, _, mess_] /; |
|||
toNumPlTxt[mess] >= n := (Message[enc::longmess, mess, n]; $Failed); |
|||
enc[n_, e_, mess_] := PowerMod[toNumPlTxt[mess], e, n]; |
|||
dec[n_, d_, en_] := fromNumPlTxt[PowerMod[en, d, n]]; |
|||
text = "The cake is a lie!"; |
|||
n = 9516311845790656153499716760847001433441357; |
|||
e = 65537; |
|||
d = 5617843187844953170308463622230283376298685; |
|||
en = enc[n, e, text]; |
|||
de = dec[n, d, en]; |
|||
Print["Text: '" <> text <> "'"]; |
|||
Print["n = " <> IntegerString[n]]; |
|||
Print["e = " <> IntegerString[e]]; |
|||
Print["d = " <> IntegerString[d]]; |
|||
Print["Numeric plaintext: " <> IntegerString[toNumPlTxt[text]]]; |
|||
Print["Encoded: " <> IntegerString[en]]; |
|||
Print["Decoded: '" <> de <> "'"];</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Text: 'The cake is a lie!' |
|||
n = 9516311845790656153499716760847001433441357 |
|||
e = 65537 |
|||
d = 5617843187844953170308463622230283376298685 |
|||
Numeric plaintext: 7352955804624388987810264523908743852287265 |
|||
Encoded: 199505409518408949879682159958576932863989 |
|||
Decoded: 'The cake is a lie!'</pre> |
|||
=={{header|Nim}}== |
|||
<syntaxhighlight lang="nim">import strutils, streams, strformat |
|||
# nimble install stint |
|||
import stint |
|||
const messages = ["PPAP", "I have a pen, I have a apple\nUh! Apple-pen!", |
|||
"I have a pen, I have pineapple\nUh! Pineapple-pen!", |
|||
"Apple-pen, pineapple-pen\nUh! Pen-pineapple-apple-pen\nPen-pineapple-apple-pen\nDance time!", "\a\0"] |
|||
const |
|||
n = u256("9516311845790656153499716760847001433441357") |
|||
e = u256("65537") |
|||
d = u256("5617843187844953170308463622230283376298685") |
|||
proc pcount(s: string, c: char): int{.inline.} = |
|||
for ch in s: |
|||
if ch != c: |
|||
break |
|||
result+=1 |
|||
func powmodHexStr(s: string, key, divisor: UInt256): string{.inline.} = |
|||
toHex(powmod(UInt256.fromHex(s), key, divisor)) |
|||
proc translate(hexString: string, key, divisor: UInt256, |
|||
encrypt = true): string = |
|||
var |
|||
strm = newStringStream(hexString) |
|||
chunk, residue, tempChunk: string |
|||
let chunkSize = len(toHex(divisor)) |
|||
while true: |
|||
tempChunk = strm.peekStr(chunkSize-int(encrypt)*3) |
|||
if len(chunk) > 0: |
|||
if len(tempChunk) == 0: |
|||
if encrypt: |
|||
result&=powmodHexStr(pcount(chunk, '0').toHex(2)&align(chunk, |
|||
chunkSize-3, '0'), key, divisor) |
|||
else: |
|||
tempChunk = align(powmodHexStr(chunk, key, divisor), chunkSize-1, '0') |
|||
residue = tempChunk[2..^1].strip(trailing = false, chars = {'0'}) |
|||
result&=align(residue, fromHex[int](tempChunk[0..1])+len(residue), '0') |
|||
break |
|||
result&=align(powmodHexStr(chunk, key, divisor), chunkSize-3+int( |
|||
encrypt)*3, '0') |
|||
discard strm.readStr(chunkSize-int(encrypt)*3) |
|||
chunk = tempChunk |
|||
strm.close() |
|||
for message in messages: |
|||
echo(&"plaintext:\n{message}") |
|||
var numPlaintext = message.toHex() |
|||
echo(&"numerical plaintext in hex:\n{numPlaintext}") |
|||
var ciphertext = translate(numPlaintext, e, n) |
|||
echo(&"ciphertext is: \n{ciphertext}") |
|||
var deciphertext = translate(ciphertext, d, n, false) |
|||
echo(&"deciphered numerical plaintext in hex is:\n{deciphertext}") |
|||
echo(&"deciphered plaintext is:\n{parseHexStr(deciphertext)}\n\n")</syntaxhighlight> |
|||
{{out}} |
|||
<pre>plaintext: |
|||
PPAP |
|||
numerical plaintext in hex: |
|||
50504150 |
|||
ciphertext is: |
|||
6c55b71c718b8921555eaa9754b7bfd7018b |
|||
deciphered numerical plaintext in hex is: |
|||
50504150 |
|||
deciphered plaintext is: |
|||
PPAP |
|||
plaintext: |
|||
I have a pen, I have a apple |
|||
Uh! Apple-pen! |
|||
numerical plaintext in hex: |
|||
49206861766520612070656E2C204920686176652061206170706C650A556821204170706C652D70656E21 |
|||
ciphertext is: |
|||
4614caba02ac33654130c10485dcceeec4a2443f4bffb46e389c2705d4ebd7ac7185a206ae0294575f283841baad236fa90d5c5536b |
|||
deciphered numerical plaintext in hex is: |
|||
49206861766520612070656e2c204920686176652061206170706c650a556821204170706c652d70656e21 |
|||
deciphered plaintext is: |
|||
I have a pen, I have a apple |
|||
Uh! Apple-pen! |
|||
plaintext: |
|||
I have a pen, I have pineapple |
|||
Uh! Pineapple-pen! |
|||
numerical plaintext in hex: |
|||
49206861766520612070656E2C204920686176652070696E656170706C650A5568212050696E656170706C652D70656E21 |
|||
ciphertext is: |
|||
4614caba02ac33654130c10485dcceeec4a21c96dd7a5048e412a16c65e274609964ffb14231b9d6a70a59380d4bbaef3c40e88afa3d |
|||
deciphered numerical plaintext in hex is: |
|||
49206861766520612070656e2c204920686176652070696e656170706c650a5568212050696e656170706c652d70656e21 |
|||
deciphered plaintext is: |
|||
I have a pen, I have pineapple |
|||
Uh! Pineapple-pen! |
|||
plaintext: |
|||
Apple-pen, pineapple-pen |
|||
Uh! Pen-pineapple-apple-pen |
|||
Pen-pineapple-apple-pen |
|||
Dance time! |
|||
numerical plaintext in hex: |
|||
4170706C652D70656E2C2070696E656170706C652D70656E0A5568212050656E2D70696E656170706C652D6170706C652D70656E0A50656E2D70696E656170706C652D6170706C652D70656E0A44616E63652074696D6521 |
|||
ciphertext is: |
|||
5d733e3979b0b43207dace453c3ec65baaff54571a3127be4ccd120dff94fb2e1b9258d6067cee2669e868ee4390c5e16f61016a171f6585ad4cd58ca3335bc9faa96da943bfedad0dd0ac7cbc83a256bf9f6f65d755865aed232e1e0a467512a6744f3f470ee283c8b4e2e5 |
|||
deciphered numerical plaintext in hex is: |
|||
4170706c652d70656e2c2070696e656170706c652d70656e0a5568212050656e2d70696e656170706c652d6170706c652d70656e0a50656e2d70696e656170706c652d6170706c652d70656e0a44616e63652074696d6521 |
|||
deciphered plaintext is: |
|||
Apple-pen, pineapple-pen |
|||
Uh! Pen-pineapple-apple-pen |
|||
Pen-pineapple-apple-pen |
|||
Dance time! |
|||
plaintext: |
|||
(shell terminal cannot display "\a\0") |
|||
numerical plaintext in hex: |
|||
0700 |
|||
ciphertext is: |
|||
2177c0b1865ac16e47807e4f4d82e421bbdf |
|||
deciphered numerical plaintext in hex is: |
|||
0700 |
|||
deciphered plaintext is: |
|||
(shell terminal cannot display "\a\0") |
|||
</pre> |
|||
=={{header|PARI/GP}}== |
|||
<syntaxhighlight lang="parigp">stigid(V,b)=subst(Pol(V),'x,b); \\ inverse function digits(...) |
|||
n = 9516311845790656153499716760847001433441357; |
|||
e = 65537; |
|||
d = 5617843187844953170308463622230283376298685; |
|||
text = "Rosetta Code" |
|||
inttext = stigid(Vecsmall(text),256) \\ message as an integer |
|||
encoded = lift(Mod(inttext, n) ^ e) \\ encrypted message |
|||
decoded = lift(Mod(encoded, n) ^ d) \\ decrypted message |
|||
message = Strchr(digits(decoded, 256)) \\ readable message</syntaxhighlight> |
|||
Output:<pre> |
|||
text: "Rosetta Code" |
|||
inttext: 25512506514985639724585018469 |
|||
encoded: 916709442744356653386978770799029131264344 |
|||
decoded: 25512506514985639724585018469 |
|||
message: "Rosetta Code" |
|||
</pre> |
|||
If inttext is equal or greater than ''b = 2^(log(n)/log(2)\1)'' use ''block = inttext % b; inttext /= b;'' to break inttext into blocks and encode piece by piece. Decode in reverse order. |
|||
As a check: it's easy to crack this weak encrypted message without knowing secret key 'd' |
|||
<syntaxhighlight lang="parigp">f = factor(n); \\ factorize public key 'n' |
|||
crack = Strchr(digits(lift(Mod(encoded,n) ^ lift(Mod(1,(f[1,1]-1)*(f[2,1]-1)) / e)),256))</syntaxhighlight> |
|||
Output:<pre>crack: "Rosetta Code"</pre> |
|||
=={{header|Perl}}== |
|||
{{trans|Raku}} |
|||
<syntaxhighlight lang="perl">use bigint; |
|||
$n = 9516311845790656153499716760847001433441357; |
|||
$e = 65537; |
|||
$d = 5617843187844953170308463622230283376298685; |
|||
package Message { |
|||
my @alphabet; |
|||
push @alphabet, $_ for 'A' .. 'Z', ' '; |
|||
my $rad = +@alphabet; |
|||
$code{$alphabet[$_]} = $_ for 0..$rad-1; |
|||
sub encode { |
|||
my($t) = @_; |
|||
my $cnt = my $sum = 0; |
|||
for (split '', reverse $t) { |
|||
$sum += $code{$_} * $rad**$cnt; |
|||
$cnt++; |
|||
} |
|||
$sum; |
|||
} |
|||
sub decode { |
|||
my($n) = @_; |
|||
my(@i); |
|||
while () { |
|||
push @i, $n % $rad; |
|||
last if $n < $rad; |
|||
$n = int $n / $rad; |
|||
} |
|||
reverse join '', @alphabet[@i]; |
|||
} |
|||
sub expmod { |
|||
my($a, $b, $n) = @_; |
|||
my $c = 1; |
|||
do { |
|||
($c *= $a) %= $n if $b % 2; |
|||
($a *= $a) %= $n; |
|||
} while ($b = int $b/2); |
|||
$c; |
|||
} |
|||
} |
|||
my $secret_message = "ROSETTA CODE"; |
|||
$numeric_message = Message::encode $secret_message; |
|||
$numeric_cipher = Message::expmod $numeric_message, $e, $n; |
|||
$text_cipher = Message::decode $numeric_cipher; |
|||
$numeric_cipher2 = Message::encode $text_cipher; |
|||
$numeric_message2 = Message::expmod $numeric_cipher2, $d, $n; |
|||
$secret_message2 = Message::decode $numeric_message2; |
|||
print <<"EOT"; |
|||
Secret message is $secret_message |
|||
Secret message in integer form is $numeric_message |
|||
After exponentiation with public exponent we get: $numeric_cipher |
|||
This turns into the string $text_cipher |
|||
If we re-encode it in integer form we get $numeric_cipher2 |
|||
After exponentiation with SECRET exponent we get: $numeric_message2 |
|||
This turns into the string $secret_message2 |
|||
EOT</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Secret message is ROSETTA CODE |
|||
Secret message in integer form is 97525102075211938 |
|||
After exponentiation with public exponent we get: 8326171774113983822045243488956318758396426 |
|||
This turns into the string ZULYDCEZOWTFXFRRNLIMGNUPHVCJSX |
|||
If we re-encode it in integer form we get 8326171774113983822045243488956318758396426 |
|||
After exponentiation with SECRET exponent we get: 97525102075211938 |
|||
This turns into the string ROSETTA CODE</pre> |
|||
=={{header|Phix}}== |
|||
{{libheader|Phix/mpfr}} |
|||
{{trans|C}} |
|||
<!--<syntaxhighlight lang="phix">(notonline)--> |
|||
<span style="color: #008080;">without</span> <span style="color: #008080;">javascript_semantics</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #000000;">builtins</span><span style="color: #0000FF;">/</span><span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"9516311845790656153499716760847001433441357"</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"65537"</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">d</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"5617843187844953170308463622230283376298685"</span><span style="color: #0000FF;">),</span> |
|||
<span style="color: #000000;">pt</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">(),</span> |
|||
<span style="color: #000000;">ct</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">plaintext</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"Rossetta Code"</span> <span style="color: #000080;font-style:italic;">-- matches C/zkl |
|||
-- "Rosetta Code" -- matches D/FreeBasic/Go/Icon/J/Kotlin/Seed7.</span> |
|||
<span style="color: #000000;">mpz_import</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">plaintext</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">plaintext</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">mpz_cmp</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)></span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ct</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">);</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Encoded: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ct</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #7060A8;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ct</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">);</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Decoded: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">)})</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">size</span> <span style="color: #0000FF;">=</span><span style="color: #7060A8;">floor</span><span style="color: #0000FF;">((</span><span style="color: #7060A8;">mpz_sizeinbase</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">7</span><span style="color: #0000FF;">)/</span><span style="color: #000000;">8</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">pMem</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">allocate</span><span style="color: #0000FF;">(</span><span style="color: #000000;">size</span><span style="color: #0000FF;">,</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">mpz_export</span><span style="color: #0000FF;">(</span><span style="color: #000000;">pMem</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">pt</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">></span><span style="color: #000000;">size</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"As String: %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #7060A8;">peek</span><span style="color: #0000FF;">({</span><span style="color: #000000;">pMem</span><span style="color: #0000FF;">,</span><span style="color: #000000;">count</span><span style="color: #0000FF;">})})</span> |
|||
<span style="color: #0000FF;">{</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ct</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_free</span><span style="color: #0000FF;">({</span><span style="color: #000000;">pt</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">ct</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">d</span><span style="color: #0000FF;">})</span> |
|||
<!--</syntaxhighlight>--> |
|||
<small>(mpz_import() and mpz_export() are not supported under pwa/p2js)</small> |
|||
{{out}} |
|||
<pre> |
|||
Encoded: 5278143020249600501803788468419399384934220 |
|||
Decoded: 6531201733672758787904906421349 |
|||
As String: Rossetta Code |
|||
</pre> |
|||
=={{header|PicoLisp}}== |
|||
PicoLisp comes with an RSA library: |
|||
<syntaxhighlight lang="picolisp">### This is a copy of "lib/rsa.l" ### |
|||
# Generate long random number |
|||
(de longRand (N) |
|||
(use (R D) |
|||
(while (=0 (setq R (abs (rand))))) |
|||
(until (> R N) |
|||
(unless (=0 (setq D (abs (rand)))) |
|||
(setq R (* R D)) ) ) |
|||
(% R N) ) ) |
|||
# X power Y modulus N |
|||
(de **Mod (X Y N) |
|||
(let M 1 |
|||
(loop |
|||
(when (bit? 1 Y) |
|||
(setq M (% (* M X) N)) ) |
|||
(T (=0 (setq Y (>> 1 Y))) |
|||
M ) |
|||
(setq X (% (* X X) N)) ) ) ) |
|||
# Probabilistic prime check |
|||
(de prime? (N) |
|||
(and |
|||
(> N 1) |
|||
(bit? 1 N) |
|||
(let (Q (dec N) K 0) |
|||
(until (bit? 1 Q) |
|||
(setq |
|||
Q (>> 1 Q) |
|||
K (inc K) ) ) |
|||
(do 50 |
|||
(NIL (_prim? N Q K)) |
|||
T ) ) ) ) |
|||
# (Knuth Vol.2, p.379) |
|||
(de _prim? (N Q K) |
|||
(use (X J Y) |
|||
(while (> 2 (setq X (longRand N)))) |
|||
(setq |
|||
J 0 |
|||
Y (**Mod X Q N) ) |
|||
(loop |
|||
(T |
|||
(or |
|||
(and (=0 J) (= 1 Y)) |
|||
(= Y (dec N)) ) |
|||
T ) |
|||
(T |
|||
(or |
|||
(and (> J 0) (= 1 Y)) |
|||
(<= K (inc 'J)) ) |
|||
NIL ) |
|||
(setq Y (% (* Y Y) N)) ) ) ) |
|||
# Find a prime number with `Len' digits |
|||
(de prime (Len) |
|||
(let P (longRand (** 10 (*/ Len 2 3))) |
|||
(unless (bit? 1 P) |
|||
(inc 'P) ) |
|||
(until (prime? P) # P: Prime number of size 2/3 Len |
|||
(inc 'P 2) ) |
|||
# R: Random number of size 1/3 Len |
|||
(let (R (longRand (** 10 (/ Len 3))) K (+ R (% (- P R) 3))) |
|||
(when (bit? 1 K) |
|||
(inc 'K 3) ) |
|||
(until (prime? (setq R (inc (* K P)))) |
|||
(inc 'K 6) ) |
|||
R ) ) ) |
|||
# Generate RSA key |
|||
(de rsaKey (N) #> (Encrypt . Decrypt) |
|||
(let (P (prime (*/ N 5 10)) Q (prime (*/ N 6 10))) |
|||
(cons |
|||
(* P Q) |
|||
(/ |
|||
(inc (* 2 (dec P) (dec Q))) |
|||
3 ) ) ) ) |
|||
# Encrypt a list of characters |
|||
(de encrypt (Key Lst) |
|||
(let Siz (>> 1 (size Key)) |
|||
(make |
|||
(while Lst |
|||
(let N (char (pop 'Lst)) |
|||
(while (> Siz (size N)) |
|||
(setq N (>> -16 N)) |
|||
(inc 'N (char (pop 'Lst))) ) |
|||
(link (**Mod N 3 Key)) ) ) ) ) ) |
|||
# Decrypt a list of numbers |
|||
(de decrypt (Keys Lst) |
|||
(mapcan |
|||
'((N) |
|||
(let Res NIL |
|||
(setq N (**Mod N (cdr Keys) (car Keys))) |
|||
(until (=0 N) |
|||
(push 'Res (char (& `(dec (** 2 16)) N))) |
|||
(setq N (>> 16 N)) ) |
|||
Res ) ) |
|||
Lst ) ) |
|||
### End of "lib/rsa.l" ### |
|||
# Generate 100-digit keys (private . public) |
|||
: (setq Keys (rsaKey 100)) |
|||
-> (14394597526321726957429995133376978449624406217727317004742182671030.... |
|||
# Encrypt |
|||
: (setq CryptText |
|||
(encrypt (car Keys) |
|||
(chop "The quick brown fox jumped over the lazy dog's back") ) ) |
|||
-> (72521958974980041245760752728037044798830723189142175108602418861716... |
|||
# Decrypt |
|||
: (pack (decrypt Keys CryptText)) |
|||
-> "The quick brown fox jumped over the lazy dog's back"</syntaxhighlight> |
|||
=={{header|PowerShell}}== |
|||
{{trans|C#}} |
|||
<syntaxhighlight lang="powershell"> |
|||
$n = [BigInt]::Parse("9516311845790656153499716760847001433441357") |
|||
$e = [BigInt]::new(65537) |
|||
$d = [BigInt]::Parse("5617843187844953170308463622230283376298685") |
|||
$plaintextstring = "Hello, Rosetta!" |
|||
$plaintext = [Text.ASCIIEncoding]::ASCII.GetBytes($plaintextstring) |
|||
[BigInt]$pt = [BigInt]::new($plaintext) |
|||
if ($n -lt $pt) {throw "`$n = $n < $pt = `$pt"} |
|||
$ct = [BigInt]::ModPow($pt, $e, $n) |
|||
"Encoded: $ct" |
|||
$dc = [BigInt]::ModPow($ct, $d, $n) |
|||
"Decoded: $dc" |
|||
$decoded = [Text.ASCIIEncoding]::ASCII.GetString($dc.ToByteArray()) |
|||
"As ASCII: $decoded" |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Encoded: 8545729659809274764853392532557102329563535 |
|||
Decoded: 173322416552962951144796590453843272 |
|||
As ASCII: Hello, Rosetta! |
|||
</pre> |
|||
=={{header|Python}}== |
=={{header|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!). |
|||
<syntaxhighlight lang="python">import binascii |
|||
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. --[[User:Erasmus|Erasmus]] 04:23, 24 March 2011 (UTC) |
|||
<lang python> |
|||
n = 9516311845790656153499716760847001433441357 # p*q = modulus |
|||
e = 65537 |
|||
d = 5617843187844953170308463622230283376298685 |
|||
message='Rosetta Code!' |
|||
print('message ', message) |
|||
hex_data = binascii.hexlify(message.encode()) |
|||
print('hex data ', hex_data) |
|||
plain_text = int(hex_data, 16) |
|||
print('plain text integer ', plain_text) |
|||
if plain_text > n: |
|||
raise Exception('plain text too large for key') |
|||
encrypted_text = pow(plain_text, e, n) |
|||
print('encrypted text integer ', encrypted_text) |
|||
decrypted_text = pow(encrypted_text, d, n) |
|||
print('decrypted text integer ', decrypted_text) |
|||
print('message ', binascii.unhexlify(hex(decrypted_text)[2:]).decode()) # [2:] slicing, to strip the 0x part |
|||
</syntaxhighlight> |
|||
{{output}} |
|||
<pre> |
|||
message Rosetta Code! |
|||
hex data b'526f736574746120436f646521' |
|||
plain text integer 6531201667836323769493764728097 |
|||
encrypted text integer 5307878626309103053766094186556322974789734 |
|||
decrypted text integer 6531201667836323769493764728097 |
|||
message Rosetta Code! |
|||
</pre> |
|||
=={{header|Racket}}== |
|||
This implementation does key generation and demonstrates digital signature as a freebie. |
|||
Thanks again to the wonderful math/number-theory package (distributed as standard). |
|||
Cutting messages into blocks has not been done. |
|||
<syntaxhighlight lang="racket">#lang racket |
|||
(require math/number-theory) |
|||
(define-logger rsa) |
|||
(current-logger rsa-logger) |
|||
;; -| STRING TO NUMBER MAPPING |---------------------------------------------------------------------- |
|||
(define (bytes->number B) ; We'll need our data in numerical form .. |
|||
(for/fold ((rv 0)) ((b B)) (+ b (* rv 256)))) |
|||
(define (number->bytes N) ; .. and back again |
|||
(define (inr n b) (if (zero? n) b (inr (quotient n 256) (bytes-append (bytes (modulo n 256)) b)))) |
|||
(inr N (bytes))) |
|||
;; -| RSA PUBLIC / PRIVATE FUNCTIONS |---------------------------------------------------------------- |
|||
;; The basic definitions... pretty well lifted from the text book! |
|||
(define ((C e n) p) |
|||
;; Just do the arithmetic to demonstrate RSA... |
|||
;; breaking large messages into blocks is something for another day. |
|||
(unless (< p n) (raise-argument-error 'C (format "(and/c integer? (</c ~a))" n) p)) |
|||
(modular-expt p e n)) |
|||
(define ((P d n) c) |
|||
(modular-expt c d n)) |
|||
;; -| RSA KEY GENERATION |---------------------------------------------------------------------------- |
|||
;; Key generation |
|||
;; Full description of the steps can be found on Wikipedia |
|||
(define (RSA-keyset function-base-name) |
|||
(log-info "RSA-keyset: ~s" function-base-name) |
|||
(define max-k 4294967087) |
|||
;; I'm guessing this RNG is about as cryptographically strong as replacing spaces with tabs. |
|||
(define (big-random n-rolls) |
|||
(for/fold ((rv 1)) ((roll (in-range n-rolls 0 -1))) (+ (* rv (add1 max-k)) 1 (random max-k)))) |
|||
(define (big-random-prime) |
|||
(define start-number (big-random (/ 1024 32))) |
|||
(log-debug "got large (possibly non-prime) number, finding next prime") |
|||
(next-prime (match start-number ((? odd? o) o) ((app add1 e) e)))) |
|||
;; [1] Choose two distinct prime numbers p and q. |
|||
(log-debug "generating p") |
|||
(define p (big-random-prime)) |
|||
(log-debug "p generated") |
|||
(log-debug "generating q") |
|||
(define q (big-random-prime)) |
|||
(log-debug "q generated") |
|||
(log-info "primes generated") |
|||
;; [2] Compute n = pq. |
|||
(define n (* p q)) |
|||
;; [3] Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1), |
|||
;; where φ is Euler's totient function. |
|||
(define φ (- n (+ p q -1))) |
|||
;; [4] Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are |
|||
;; coprime. ... most commonly 2^16 + 1 = 65,537 ... |
|||
(define e (+ (expt 2 16) 1)) |
|||
;; [5] Determine d as d ≡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)). |
|||
(log-debug "generating d") |
|||
(define d (modular-inverse e φ)) |
|||
(log-info "d generated") |
|||
(values n e d)) |
|||
;; -| GIVE A USABLE SET OF PRIVATE STUFF TO A USER |-------------------------------------------------- |
|||
;; six values: the public (encrypt) function (numeric) |
|||
;; the private (decrypt) function (numeric) |
|||
;; the public (encrypt) function (bytes) |
|||
;; the private (decrypt) function (bytes) |
|||
;; private (list n e d) |
|||
;; public (list n e) |
|||
(define (RSA-key-pack #:function-base-name function-base-name) |
|||
(define (rnm-fn f s) (procedure-rename f (string->symbol (format "~a-~a" function-base-name s)))) |
|||
(define-values (n e d) (RSA-keyset function-base-name)) |
|||
(define my-C (rnm-fn (C e n) "C")) |
|||
(define my-P (rnm-fn (P d n) "P")) |
|||
(define my-encrypt (rnm-fn (compose number->bytes my-C bytes->number) "encrypt")) |
|||
(define my-decrypt (rnm-fn (compose number->bytes my-P bytes->number) "decrypt")) |
|||
(values my-C my-P my-encrypt my-decrypt (list n e d) (list n e))) |
|||
;; -| HEREON IS JUST A LOAD OF CHATTY DEMOS |--------------------------------------------------------- |
|||
(define (narrated-encrypt-bytes C who plain-text) |
|||
(define plain-n (bytes->number plain-text)) |
|||
(define cypher-n (C plain-n)) |
|||
(define cypher-text (number->bytes cypher-n)) |
|||
(printf #<<EOS |
|||
~a wants to send plain text: ~s |
|||
as number: ~s |
|||
cyphered number: ~s |
|||
sent by ~a over the public interwebs: |
|||
~s |
|||
... |
|||
EOS |
|||
who plain-text plain-n cypher-n who cypher-text) |
|||
cypher-text) |
|||
(define (narrated-decrypt-bytes P who cypher-text) |
|||
(define cypher-n (bytes->number cypher-text)) |
|||
(define plain-n (P cypher-n)) |
|||
(define plain-text (number->bytes plain-n)) |
|||
(printf #<<EOS |
|||
... |
|||
~s |
|||
received by ~a |
|||
as number: ~s |
|||
decyphered (with P) number: ~s |
|||
decyphered text: |
|||
~s |
|||
EOS |
|||
cypher-text who cypher-n plain-n plain-text) |
|||
plain-text) |
|||
;; ENCRYPT AND DECRYPT A MESSAGE WITH THE e.g. KEYS |
|||
(define-values (given-n given-e given-d) |
|||
(values 9516311845790656153499716760847001433441357 |
|||
65537 |
|||
5617843187844953170308463622230283376298685)) |
|||
;; Get the keys specific RSA functions |
|||
(for ((message-text (list #"hello world" #"TOP SECRET!"))) |
|||
(define Bobs-public-function (C given-e given-n)) |
|||
(define Bobs-private-function (P given-d given-n)) |
|||
(define cypher-text (narrated-encrypt-bytes Bobs-public-function "Alice" message-text)) |
|||
(define plain-text (narrated-decrypt-bytes Bobs-private-function "Bob" cypher-text)) |
|||
plain-text) |
|||
;; Demonstrate with larger keys. |
|||
;; (And include a free recap on digital signatures, too) |
|||
(define-values (A-pub-C A-pvt-P A-pub-encrypt A-pvt-decrypt A-pvt-keys A-pub-keys) |
|||
(RSA-key-pack #:function-base-name 'Alice)) |
|||
(define-values (B-pub-C B-pvt-P B-pub-encrypt B-pvt-decrypt B-pvt-keys B-pub-keys) |
|||
(RSA-key-pack #:function-base-name 'Bob)) |
|||
;; Since p and q are random, it is possible that message' = "message modulo {A,B}-key-n" will be too |
|||
;; big for "message' modulo {B,A}-key-n", if that happens then I run the program again until it |
|||
;; works. Strictly, we need blocking of the signed message -- which is not yet implemented. |
|||
(let* ((plain-A-to-B #"Dear Bob, meet you in Lymm at 1200, Alice") |
|||
(signed-A-to-B (A-pvt-decrypt plain-A-to-B)) |
|||
(unsigned-A-to-B (A-pub-encrypt signed-A-to-B)) |
|||
(crypt-signed-A-to-B (B-pub-encrypt signed-A-to-B)) |
|||
(decrypt-signed-A-to-B (B-pvt-decrypt crypt-signed-A-to-B)) |
|||
(decrypt-verified-B (A-pub-encrypt decrypt-signed-A-to-B))) |
|||
(printf |
|||
#<<EOS |
|||
Alice wants to send ~s to Bob. |
|||
She "encrypts" with her private "decryption" key. |
|||
(A-prv msg) -> ~s |
|||
Only she could have done this (only she has the her private key data) -- so this is a signature on the |
|||
message. Anyone can verify the signature by "decrypting" the message with the public "encryption" key. |
|||
(A-pub (A-prv msg)) -> ~s |
|||
But anyone is able to do this, so there is no privacy here. |
|||
Everyone knows that it can only be Alice at Lymm at noon, but this message is for Bob's eyes only. |
|||
We need to encrypt this with his public key: |
|||
(B-pub (A-prv msg)) -> ~s |
|||
Which is what gets posted to alt.chat.secret-rendezvous |
|||
Bob decrypts this to get the signed message from Alice: |
|||
(B-prv (B-pub (A-prv msg))) -> ~s |
|||
And verifies Alice's signature: |
|||
(A-pub (B-prv (B-pub (A-prv msg)))) -> ~s |
|||
Alice genuinely sent the message. |
|||
And nobody else (on a.c.s-r, at least) has read it. |
|||
KEYS: |
|||
Alice's full set: ~s |
|||
Bob's full set: ~s |
|||
EOS |
|||
plain-A-to-B signed-A-to-B unsigned-A-to-B crypt-signed-A-to-B decrypt-signed-A-to-B |
|||
decrypt-verified-B A-pvt-keys B-pvt-keys))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>Alice wants to send plain text: #"hello world" |
|||
as number: 126207244316550804821666916 |
|||
cyphered number: 4109627268073579506944196826730512948879423 |
|||
sent by Alice over the public interwebs: |
|||
#"/-\e\355\225\327\244\222<R@\20\4\233\275\333`?" |
|||
... |
|||
... |
|||
#"/-\e\355\225\327\244\222<R@\20\4\233\275\333`?" |
|||
received by Bob |
|||
as number: 4109627268073579506944196826730512948879423 |
|||
decyphered (with P) number: 126207244316550804821666916 |
|||
decyphered text: |
|||
#"hello world" |
|||
Alice wants to send plain text: #"TOP SECRET!" |
|||
as number: 101924313868583037137409057 |
|||
cyphered number: 5346093164296793050289700489360581430628365 |
|||
sent by Alice over the public interwebs: |
|||
#"=^\301{\17p\201AE\341D\357 \237IPP\r" |
|||
... |
|||
... |
|||
#"=^\301{\17p\201AE\341D\357 \237IPP\r" |
|||
received by Bob |
|||
as number: 5346093164296793050289700489360581430628365 |
|||
decyphered (with P) number: 101924313868583037137409057 |
|||
decyphered text: |
|||
#"TOP SECRET!" |
|||
Alice wants to send #"Dear Bob, meet you in Lymm at 1200, Alice" to Bob. |
|||
She "encrypts" with her private "decryption" key. |
|||
(A-prv msg) -> #"B}\4<G\373-\217\350;\0214\226\233\236\333\215\226\225=\236\350\277X\241*J\356\302\250\350fO\5\375u\367\365\315\270\312\334\204U\332\224\322\357u=\262\326\274e\31\301\321\210:i\361\361g\361\16\5a\304X\306\313\350(^\374 \353\350t\2662\305\346a\300\244b\337JI\343\335\21j\202\236\242\335<rA\a\233\375\23\t\32(d`\237i\267\336\270\340L\26\f\260\346&\t\301\326\331k@\253\242\241VKw\365 \204U\270*\r,\334h=\257\230\320V\357\304\242\4B\240\356\200\204\252\35\20c\220LJ}\275x!\25\23\262\325{\246\304?\36\272\343\17\230\2449Q[y\334(m1\252N<\253?^#\236p\311\3006\f\245M*<\273H\333\225\256\317\322\363\273\335\303\243\354\a\253\342\312\302\372vTQ\247\r\210\343\264\323*E\364\2\ba\305Z79\273M\327\310F\301,\235\32\323" |
|||
Only she could have done this (only she has the her private key data) -- so this is a signature on the |
|||
message. Anyone can verify the signature by "decrypting" the message with the public "encryption" key. |
|||
(A-pub (A-prv msg)) -> #"Dear Bob, meet you in Lymm at 1200, Alice" |
|||
But anyone is able to do this, so there is no privacy here. |
|||
Everyone knows that it can only be Alice at Lymm at noon, but this message is for Bob's eyes only. |
|||
We need to encrypt this with his public key: |
|||
(B-pub (A-prv msg)) -> #"\eXq\4/\207\250hs\244<ym\3716\210\357'0\351E\202D\360\177\361\325\24\310+s\340j1\36\0\213\353\254\314*\212a;\300\210\\\347\371z`\226\230 \230A\337d\31\262nwp\6m\312\320D@h\232d]{sN\312xAW\216'c\27V\5\270\267>@\305\312\210\262|tGU?\266\325\250\227\270X\235\6C\307\323D\301q{\266S\351,i\211,~X\341\225z4\320F\353\361I\313M\270&d\267m\207 \2736s_\272\307\275\31T\301\247\317@\16D\263X\"\340\262\204\277g\30\337\311o\205\236\34\370)\323\275\5\1\301>\226Q,\255\213\\\2\307\215c\342\323\16\226a\3U\254\214\275\274\214\325\f\226\347\325\225\354~\32z)\340re5I\321\254\34'T\n\220p\316#\1\347\6;*\347\303\351\342\221\244\eey\31\275y\271\2605y\344\261\202B\321E\335\212" |
|||
Which is what gets posted to alt.chat.secret-rendezvous |
|||
Bob decrypts this to get the signed message from Alice: |
|||
(B-prv (B-pub (A-prv msg))) -> #"B}\4<G\373-\217\350;\0214\226\233\236\333\215\226\225=\236\350\277X\241*J\356\302\250\350fO\5\375u\367\365\315\270\312\334\204U\332\224\322\357u=\262\326\274e\31\301\321\210:i\361\361g\361\16\5a\304X\306\313\350(^\374 \353\350t\2662\305\346a\300\244b\337JI\343\335\21j\202\236\242\335<rA\a\233\375\23\t\32(d`\237i\267\336\270\340L\26\f\260\346&\t\301\326\331k@\253\242\241VKw\365 \204U\270*\r,\334h=\257\230\320V\357\304\242\4B\240\356\200\204\252\35\20c\220LJ}\275x!\25\23\262\325{\246\304?\36\272\343\17\230\2449Q[y\334(m1\252N<\253?^#\236p\311\3006\f\245M*<\273H\333\225\256\317\322\363\273\335\303\243\354\a\253\342\312\302\372vTQ\247\r\210\343\264\323*E\364\2\ba\305Z79\273M\327\310F\301,\235\32\323" |
|||
And verifies Alice's signature: |
|||
(A-pub (B-prv (B-pub (A-prv msg)))) -> #"Dear Bob, meet you in Lymm at 1200, Alice" |
|||
Alice genuinely sent the message. |
|||
And nobody else (on a.c.s-r, at least) has read it. |
|||
KEYS: |
|||
Alice's full set: (104685401856522903402850023081275254628934665755538824520013952439504139625115997713509448983980532229245117213463882915048453185855818576471069794363975118091990355601850994380420233190180031768156385491949949615002445375960925665247160785747787333124376845288066200576472845984390877385677186819996627676676634639097055255729270941154875343472575964213139374388405182305309760553726485659960423106167598201105611690471457085541574734821426421348095213778701793437599877207476950721505461275161623234401077010666082709757697115644957960465476529769011591060857755043525709942747005873747546230596592939772042294065813 65537 2717089103223300710869400327467677924284264864888101995949520623458451584636500177162207191689440855119183734075439291369721208922299577316283774359722319847940485449116507338466741179127763462435479373816422239271238530669843516739939583694050479174276592059981393826091830737132442474221232201364332570578846365932454353567371199951546467136016124284306002875511872761969350668537869576342139916560099770887726733315363999637008436783521647128919138309876487426046116064403375745886449924998134881929018589019826525209406457786746758225025770316010686323085528641486882271019011944746635302695471929361680924424193) |
|||
Bob's full set: (66453628687555934925745945778628604864426900808865010224295559035622434292221884343034084372211796572669001844069872620681089178469116242843088008182594366670325110214571956032739850447309116856946000976960287962443982329056724158946509616005091553738944083845350969457626620995817549009173612137879065054069514627974682257866567361928526254468372096924822844681482943840826594855542477801468633973217959659919448029041762191501507078772425126221108904380853918736930072466664169841898502073182029626689571748335731893924787111612947107622008163390629359277338946499436753837554940480109336784185532913066463754681017 65537 40065645823449313467522156271281139875308606308813084959528059327930012759030216763756439504389958618427304726562596348031980052624474573194667691034359998325290386803002604616043604539794698176121997293172282195706991070204897106862588071733664686557012032668284371518061563321600604452438728297053809260134398419618573423334221995863281726034127469856978901426632431740449516515840848181614406772903883730243825332015822633960435748349249507976445585019837204822017018926054553157019477128528700400452557614873387735038266042290443427594857847964184247833486305612600841625002197933394323058877499979801727736278613)</pre> |
|||
The burden seems to be in finding (proving) the next large prime after the big random number. |
|||
However, once keys are generated, things are pretty snappy. |
|||
=={{header|Raku}}== |
|||
(formerly Perl 6) |
|||
No blocking here. Algorithm doesn't really work if either red or black text begins with 'A'. |
|||
<syntaxhighlight lang="raku" line>class RSA-message { |
|||
has ($.n, $.e, $.d); # the 3 elements that define an RSA key |
|||
my @alphabet = |('A' .. 'Z'), ' '; |
|||
my $rad = +@alphabet; |
|||
my %code = @alphabet Z=> 0 .. *; |
|||
subset Text of Str where /^^ @alphabet+ $$/; |
|||
method encode(Text $t) { |
|||
[+] %code{$t.flip.comb} Z× (1, $rad, $rad×$rad … *); |
|||
} |
|||
method decode(Int $n is copy) { |
|||
@alphabet[ |
|||
gather loop { |
|||
take $n % $rad; |
|||
last if $n < $rad; |
|||
$n div= $rad; |
|||
} |
|||
].join.flip; |
|||
} |
|||
} |
|||
constant $n = 9516311845790656153499716760847001433441357; |
|||
constant $e = 65537; |
|||
constant $d = 5617843187844953170308463622230283376298685; |
|||
my $fmt = "%48s %s\n"; |
|||
my $message = 'ROSETTA CODE'; |
|||
printf $fmt, 'Secret message is', $message; |
|||
my $rsa = RSA-message.new: n => $n, e => $e, d => $d; |
|||
printf $fmt, 'Secret message in integer form is', |
|||
my $numeric-message = $rsa.encode: $message; |
|||
printf $fmt, 'After exponentiation with public exponent we get', |
|||
my $numeric-cipher = expmod $numeric-message, $e, $n; |
|||
printf $fmt, 'This turns into the string', |
|||
my $text-cipher = $rsa.decode: $numeric-cipher; |
|||
printf $fmt, 'If we re-encode it in integer form we get', |
|||
my $numeric-cipher2 = $rsa.encode: $text-cipher; |
|||
printf $fmt, 'After exponentiation with SECRET exponent we get', |
|||
my $numeric-message2 = expmod $numeric-cipher2, $d, $n; |
|||
printf $fmt, 'This turns into the string', |
|||
my $message2 = $rsa.decode: $numeric-message2; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> Secret message is ROSETTA CODE |
|||
Secret message in integer form is 97525102075211938 |
|||
After exponentiation with public exponent we get 8326171774113983822045243488956318758396426 |
|||
This turns into the string ZULYDCEZOWTFXFRRNLIMGNUPHVCJSX |
|||
If we re-encode it in integer form we get 8326171774113983822045243488956318758396426 |
|||
After exponentiation with SECRET exponent we get 97525102075211938 |
|||
This turns into the string ROSETTA CODE</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight lang="ruby"> |
|||
#!/usr/bin/ruby |
|||
require 'openssl' # for mod_exp only |
|||
require 'prime' |
|||
def rsa_encode blocks, e, n |
|||
blocks.map{|b| b.to_bn.mod_exp(e, n).to_i} |
|||
end |
|||
def rsa_decode ciphers, d, n |
|||
rsa_encode ciphers, d, n |
|||
end |
|||
# all numbers in blocks have to be < modulus, or information is lost |
|||
# for secure encryption only use big modulus and blocksizes |
|||
def text_to_blocks text, blocksize=64 # 1 hex = 4 bit => default is 256bit |
|||
text.each_byte.reduce(""){|acc,b| acc << b.to_s(16).rjust(2, "0")} # convert text to hex (preserving leading 0 chars) |
|||
.each_char.each_slice(blocksize).to_a # slice hexnumbers in pieces of blocksize |
|||
.map{|a| a.join("").to_i(16)} # convert each slice into internal number |
|||
end |
|||
def blocks_to_text blocks |
|||
blocks.map{|d| d.to_s(16)}.join("") # join all blocks into one hex-string |
|||
.each_char.each_slice(2).to_a # group into pairs |
|||
.map{|s| s.join("").to_i(16)} # number from 2 hexdigits is byte |
|||
.flatten.pack("C*") # pack bytes into ruby-string |
|||
.force_encoding(Encoding::default_external) # reset encoding |
|||
end |
|||
def generate_keys p1, p2 |
|||
n = p1 * p2 |
|||
t = (p1 - 1) * (p2 - 1) |
|||
e = 2.step.each do |i| |
|||
break i if i.gcd(t) == 1 |
|||
end |
|||
d = 1.step.each do |i| |
|||
break i if (i * e) % t == 1 |
|||
end |
|||
return e, d, n |
|||
end |
|||
p1, p2 = Prime.take(100).last(2) |
|||
public_key, private_key, modulus = |
|||
generate_keys p1, p2 |
|||
print "Message: " |
|||
message = gets |
|||
blocks = text_to_blocks message, 4 # very small primes |
|||
print "Numbers: "; p blocks |
|||
encoded = rsa_encode(blocks, public_key, modulus) |
|||
print "Encrypted as: "; p encoded |
|||
decoded = rsa_decode(encoded, private_key, modulus) |
|||
print "Decrypted to: "; p decoded |
|||
final = blocks_to_text(decoded) |
|||
print "Decrypted Message: "; puts final |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
% echo "☆ rosettacode.org ✓" | ./rsa.rb |
|||
Message: Numbers: [58008, 34336, 29295, 29541, 29812, 24931, 28516, 25902, 28530, 26400, 58012, 37642] |
|||
Encrypted as: [8509, 99626, 21784, 139807, 81066, 67678, 183438, 147659, 261822, 85962, 150227, 167121] |
|||
Decrypted to: [58008, 34336, 29295, 29541, 29812, 24931, 28516, 25902, 28530, 26400, 58012, 37642] |
|||
Decrypted Message: ☆ rosettacode.org ✓ |
|||
</pre> |
|||
=={{header|Rust}}== |
|||
<syntaxhighlight lang="rust"> |
|||
extern crate num; |
|||
use num::bigint::BigUint; |
|||
use num::integer::Integer; |
|||
use num::traits::{One, Zero}; |
|||
fn mod_exp(b: &BigUint, e: &BigUint, n: &BigUint) -> Result<BigUint, &'static str> { |
|||
if n.is_zero() { |
|||
return Err("modulus is zero"); |
|||
} |
|||
if b >= n { |
|||
// base is too large and should be split into blocks |
|||
return Err("base is >= modulus"); |
|||
} |
|||
if b.gcd(n) != BigUint::one() { |
|||
return Err("base and modulus are not relatively prime"); |
|||
} |
|||
let mut bb = b.clone(); |
|||
let mut ee = e.clone(); |
|||
let mut result = BigUint::one(); |
|||
while !ee.is_zero() { |
|||
if ee.is_odd() { |
|||
result = (result * &bb) % n; |
|||
} |
|||
ee >>= 1; |
|||
bb = (&bb * &bb) % n; |
|||
} |
|||
Ok(result) |
|||
} |
|||
fn main() { |
|||
let msg = "Rosetta Code"; |
|||
let n = "9516311845790656153499716760847001433441357" |
|||
.parse() |
|||
.unwrap(); |
|||
let e = "65537".parse().unwrap(); |
|||
let d = "5617843187844953170308463622230283376298685" |
|||
.parse() |
|||
.unwrap(); |
|||
let msg_int = BigUint::from_bytes_be(msg.as_bytes()); |
|||
let enc = mod_exp(&msg_int, &e, &n).unwrap(); |
|||
let dec = mod_exp(&enc, &d, &n).unwrap(); |
|||
let msg_dec = String::from_utf8(dec.to_bytes_be()).unwrap(); |
|||
println!("msg as txt: {}", msg); |
|||
println!("msg as num: {}", msg_int); |
|||
println!("enc as num: {}", enc); |
|||
println!("dec as num: {}", dec); |
|||
println!("dec as txt: {}", msg_dec); |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
msg as txt: Rosetta Code |
|||
msg as num: 25512506514985639724585018469 |
|||
enc as num: 916709442744356653386978770799029131264344 |
|||
dec as num: 25512506514985639724585018469 |
|||
dec as txt: Rosetta Code |
|||
</pre> |
|||
=={{header|Scala}}== |
|||
from tkinter import * |
|||
The code below demonstrates RSA encryption and decryption in Scala. Text to integer encryption using ASCII code. |
|||
import random |
|||
<syntaxhighlight lang="scala"> |
|||
import time |
|||
object RSA_saket{ |
|||
val d = BigInt("5617843187844953170308463622230283376298685") |
|||
val n = BigInt("9516311845790656153499716760847001433441357") |
|||
val e = 65537 |
|||
val text = "Rosetta Code" |
|||
val encode = (msg:BigInt) => pow_mod(msg,e,n) |
|||
val decode = (msg:BigInt) => pow_mod(msg,d,n) |
|||
val getmsg = (txt:String) => BigInt(txt.map(x => "%03d".format(x.toInt)).reduceLeft(_+_)) |
|||
def pow_mod(p:BigInt, q:BigInt, n:BigInt):BigInt = { |
|||
if(q==0) BigInt(1) |
|||
else if(q==1) p |
|||
else if(q%2 == 1) pow_mod(p,q-1,n)*p % n |
|||
else pow_mod(p*p % n,q/2,n) |
|||
} |
|||
def gettxt(num:String) = { |
|||
if(num.size%3==2) |
|||
("0" + num).grouped(3).toList.foldLeft("")(_ + _.toInt.toChar) |
|||
else |
|||
num.grouped(3).toList.foldLeft("")(_ + _.toInt.toChar) |
|||
} |
|||
def main(args: Array[String]): Unit = { |
|||
println(f"Original String \t: "+text) |
|||
val msg = getmsg(text) |
|||
println(f"Converted Signal \t: "+msg) |
|||
val enc_sig = encode(msg) |
|||
println("Encoded Signal \t\t: "+ enc_sig) |
|||
val dec_sig = decode(enc_sig) |
|||
println("Decoded String \t\t: "+ dec_sig) |
|||
val rec_msg = gettxt(dec_sig.toString) |
|||
println("Retrieved Signal \t: "+rec_msg) |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
letter = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q", |
|||
Ouput: |
|||
"r","s","t","u","v","w","x","y","z",",",".","!","?",' '] |
|||
Original String : Rosetta Code |
|||
number = ["01","02","03","04","05","06","07","08","09","10","11","12","13", |
|||
Converted String : 82111115101116116097032067111100101 |
|||
"14","15","16","17","18","19","20","21","22","23","24","25","26","27", |
|||
Encoded Signal : 5902559240035849005218240192859088445397686 |
|||
"28","29","30",'31'] |
|||
Decoded String : 82111115101116116097032067111100101 |
|||
Retrieved String : Rosetta Code |
|||
</pre> |
|||
=={{header|Seed7}}== |
|||
n = 2537 |
|||
<syntaxhighlight lang="seed7">$ include "seed7_05.s7i"; |
|||
e = 13 |
|||
include "bigint.s7i"; |
|||
d = 937 |
|||
include "bytedata.s7i"; |
|||
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) |
|||
const proc: main is func |
|||
def cipher(b,e): |
|||
local |
|||
# Performs the Encryption function on a block of ciphertext |
|||
const string: plainText is "Rosetta Code"; |
|||
if e == 0: |
|||
# Use a key big enough to hold 16 bytes of plain text in a single block. |
|||
return 1 |
|||
const bigInteger: modulus is 9516311845790656153499716760847001433441357_; |
|||
if e == 1: |
|||
const bigInteger: encode is 65537_; |
|||
return b |
|||
const bigInteger: decode is 5617843187844953170308463622230283376298685_; |
|||
w,r = divmod(e,2) |
|||
var bigInteger: plainTextNumber is 0_; |
|||
if r == 1: |
|||
var bigInteger: encodedNumber is 0_; |
|||
return cipher(b*b%n,w)*b%n |
|||
var bigInteger: decodedNumber is 0_; |
|||
else: |
|||
var string: decodedText is ""; |
|||
return cipher(b*b%n,w) |
|||
begin |
|||
writeln("Plain text: " <& plainText); |
|||
def group(j,h,z): |
|||
plainTextNumber := bytes2BigInt(plainText, UNSIGNED, BE); |
|||
# Places the plaintext numbers into blocks for encryption |
|||
if plainTextNumber >= modulus then |
|||
for i in range(int(j)): |
|||
writeln("Plain text message too long"); |
|||
else |
|||
for n in range(h): |
|||
writeln("Plain text as a number: " <& plainTextNumber); |
|||
y += int(numP[(h*i)+n])*(10**(z-2*n)) |
|||
encodedNumber := modPow(plainTextNumber, encode, modulus); |
|||
X.append(int(y)) |
|||
writeln("Encoded: " <& encodedNumber); |
|||
decodedNumber := modPow(encodedNumber, decode, modulus); |
|||
writeln("Decoded: " <& decodedNumber); |
|||
decodedText := bytes(decodedNumber, UNSIGNED, BE); |
|||
writeln("Decoded number as text: " <& decodedText); |
|||
end if; |
|||
end func;</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Plain text: Rosetta Code |
|||
Plain text as a number: 25512506514985639724585018469 |
|||
Encoded: 916709442744356653386978770799029131264344 |
|||
Decoded: 25512506514985639724585018469 |
|||
Decoded number as text: Rosetta Code |
|||
</pre> |
|||
=={{header|Sidef}}== |
|||
{{trans|Raku}} |
|||
<syntaxhighlight lang="ruby">const n = 9516311845790656153499716760847001433441357 |
|||
const e = 65537 |
|||
const d = 5617843187844953170308463622230283376298685 |
|||
module Message { |
|||
class App: |
|||
var alphabet = [('A' .. 'Z')..., ' '] |
|||
# Creates a Tkineter window, for ease of operation |
|||
var rad = alphabet.len |
|||
def __init__(self, master): |
|||
var code = Hash(^rad -> map {|i| (alphabet[i], i) }...) |
|||
func encode(String t) { |
|||
[code{t.reverse.chars...}] ~Z* t.len.range.map { |i| rad**i } -> sum(0) |
|||
} |
|||
func decode(Number n) { |
|||
''.join(alphabet[ |
|||
gather { |
|||
loop { |
|||
var (d, m) = n.divmod(rad) |
|||
take(m) |
|||
break if (n < rad) |
|||
n = d |
|||
} |
|||
}...] |
|||
).reverse |
|||
} |
|||
} |
|||
var secret_message = "ROSETTA CODE" |
|||
frame = Frame(master) |
|||
say "Secret message is #{secret_message}" |
|||
frame.grid() |
|||
var numeric_message = Message::encode(secret_message) |
|||
#create a button with the quit command, and tell it where to go |
|||
say "Secret message in integer form is #{numeric_message}" |
|||
quitbutton = Button(frame, text = "quit", fg ="red", |
|||
command = root.quit, width = 10) |
|||
quitbutton.grid(row = 0, column =3) |
|||
var numeric_cipher = expmod(numeric_message, e, n) |
|||
#create an entry box, tell it where it goes, and how large it is |
|||
say "After exponentiation with public exponent we get: #{numeric_cipher}" |
|||
entry = Entry(frame, width = 100) |
|||
entry.grid(row = 0, column = 0) |
|||
var text_cipher = Message::decode(numeric_cipher) |
|||
#set initial content of the entry box |
|||
say "This turns into the string #{text_cipher}" |
|||
self.contents = StringVar() |
|||
self.contents.set("Type message here") |
|||
entry["textvariable"] = self.contents |
|||
var numeric_cipher2 = Message::encode(text_cipher) |
|||
# Create a button which initializes the decryption of ciphertext |
|||
say "If we re-encode it in integer form we get #{numeric_cipher2}" |
|||
decrypt = Button(frame,text = "Decrypt", fg = "blue", |
|||
command = self.Decrypt) |
|||
decrypt.grid(row = 2, column = 1) |
|||
var numeric_message2 = expmod(numeric_cipher2, d, n) |
|||
#create a label to display the number of ciphertext blocks in an encoded message |
|||
say "After exponentiation with SECRET exponent we get: #{numeric_message2}" |
|||
label = Label(frame, text = "# of blocks") |
|||
label.grid(row = 1, column = 1) |
|||
var secret_message2 = Message::decode(numeric_message2) |
|||
#creates a button which initializes the encryption of plaintext |
|||
say "This turns into the string #{secret_message2}"</syntaxhighlight> |
|||
encrypt = Button(frame, text="Encrypt", fg = "blue", |
|||
{{out}} |
|||
command = self.Encrypt) |
|||
<pre> |
|||
encrypt.grid(row =0, column =1) |
|||
Secret message is ROSETTA CODE |
|||
Secret message in integer form is 97525102075211938 |
|||
After exponentiation with public exponent we get: 8326171774113983822045243488956318758396426 |
|||
This turns into the string ZULYDCEZOWTFXFRRNLIMGNUPHVCJSX |
|||
If we re-encode it in integer form we get 8326171774113983822045243488956318758396426 |
|||
After exponentiation with SECRET exponent we get: 97525102075211938 |
|||
This turns into the string ROSETTA CODE |
|||
</pre> |
|||
=={{header|Tcl}}== |
|||
#create an entry box for the value of "n" |
|||
This code is careful to avoid the assumption that the input string is in a single-byte encoding, instead forcing the encryption to be performed on the UTF-8 form of the text. <!-- NB: Doesn't print the intermediate encoded value; see talk page for discussion why. --> |
|||
nbox = Entry(frame, width = 100) |
|||
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
|||
nbox.grid(row = 3, column = 0) |
|||
# This is a straight-forward square-and-multiply implementation that relies on |
|||
self.n = StringVar() |
|||
# Tcl 8.5's bignum support (based on LibTomMath) for speed. |
|||
self.n.set(n) |
|||
proc modexp {b expAndMod} { |
|||
nbox["textvar"] = self.n |
|||
lassign $expAndMod -> e 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 |
|||
if {$b >= $n} {puts stderr "WARNING: modulus too small"} |
|||
for {set r 1} {$e != 0} {set e [expr {$e >> 1}]} { |
|||
if {$e & 1} { |
|||
set r [expr {($r * $b) % $n}] |
|||
} |
|||
set b [expr {($b ** 2) % $n}] |
|||
} |
|||
return $r |
|||
} |
|||
# Assumes that messages are shorter than the modulus |
|||
nlabel = Label(frame, text = "the value of 'n'") |
|||
proc rsa_encrypt {message publicKey} { |
|||
nlabel.grid(row = 3, column = 1) |
|||
if {[lindex $publicKey 0] ne "publicKey"} {error "key handling"} |
|||
set toEnc 0 |
|||
foreach char [split [encoding convertto utf-8 $message] ""] { |
|||
set toEnc [expr {$toEnc * 256 + [scan $char "%c"]}] |
|||
} |
|||
return [modexp $toEnc $publicKey] |
|||
} |
|||
proc rsa_decrypt {encrypted privateKey} { |
|||
#create an entry box for the value of "e" |
|||
if {[lindex $privateKey 0] ne "privateKey"} {error "key handling"} |
|||
ebox = Entry(frame, width = 100) |
|||
set toDec [modexp $encrypted $privateKey] |
|||
ebox.grid(row = 4, column = 0) |
|||
for {set message ""} {$toDec > 0} {set toDec [expr {$toDec >> 8}]} { |
|||
append message [format "%c" [expr {$toDec & 255}]] |
|||
} |
|||
return [encoding convertfrom utf-8 [string reverse $message]] |
|||
} |
|||
# Assemble packaged public and private keys |
|||
self.e = StringVar() |
|||
set e 65537 |
|||
self.e.set(e) |
|||
set n 9516311845790656153499716760847001433441357 |
|||
ebox["textvar"] = self.e |
|||
set d 5617843187844953170308463622230283376298685 |
|||
ebox.bind('<Key-Return>', self.set_e) |
|||
set publicKey [list "publicKey" $e $n] |
|||
set privateKey [list "privateKey" $d $n] |
|||
# Test on some input strings |
|||
elabel = Label(frame, text = "the value of 'e'") |
|||
foreach input {"Rosetta Code" "UTF-8 \u263a test"} { |
|||
elabel.grid(row = 4, column = 1) |
|||
set enc [rsa_encrypt $input $publicKey] |
|||
set dec [rsa_decrypt $enc $privateKey] |
|||
puts "$input -> $enc -> $dec" |
|||
}</syntaxhighlight> |
|||
Output: |
|||
<pre> |
|||
Rosetta Code -> 916709442744356653386978770799029131264344 -> Rosetta Code |
|||
UTF-8 ☺ test -> 3905697186829810541171404594906488782823186 -> UTF-8 ☺ test |
|||
</pre> |
|||
=={{header|Visual Basic .NET}}== |
|||
#create an entry box for the value of "d" |
|||
{{trans|C#}} |
|||
dbox = Entry(frame, width = 100) |
|||
{{libheader|System.Numerics}} |
|||
dbox.grid(row =5, column = 0) |
|||
<syntaxhighlight lang="vbnet">Imports System |
|||
Imports System.Numerics |
|||
Imports System.Text |
|||
Module Module1 |
|||
self.d = StringVar() |
|||
Sub Main() |
|||
Dim n As BigInteger = BigInteger.Parse("9516311845790656153499716760847001433441357") |
|||
dbox["textvar"] = self.d |
|||
Dim e As BigInteger = 65537 |
|||
dbox.bind('<Key-Return>', self.set_d) |
|||
Dim d As BigInteger = BigInteger.Parse("5617843187844953170308463622230283376298685") |
|||
Dim plainTextStr As String = "Hello, Rosetta!" |
|||
Dim plainTextBA As Byte() = ASCIIEncoding.ASCII.GetBytes(plainTextStr) |
|||
Dim pt As BigInteger = New BigInteger(plainTextBA) |
|||
If pt > n Then Throw New Exception() ' Blocking not implemented |
|||
Dim ct As BigInteger = BigInteger.ModPow(pt, e, n) |
|||
Console.WriteLine(" Encoded: " & ct.ToString("X")) |
|||
Dim dc As BigInteger = BigInteger.ModPow(ct, d, n) |
|||
Console.WriteLine(" Decoded: " & dc.ToString("X")) |
|||
Dim decoded As String = ASCIIEncoding.ASCII.GetString(dc.ToByteArray()) |
|||
Console.WriteLine("As ASCII: " & decoded) |
|||
End Sub |
|||
End Module</syntaxhighlight> |
|||
{{out}} |
|||
<pre> Encoded: 6219A470D8B319A31C8E13F612B31337098F |
|||
Decoded: 2161747465736F52202C6F6C6C6548 |
|||
As ASCII: Hello, Rosetta!</pre> |
|||
=={{header|V (Vlang)}}== |
|||
dlabel = Label(frame, text = "the value of 'd'") |
|||
{{trans|Go}} |
|||
dlabel.grid(row = 5, column =1) |
|||
<syntaxhighlight lang="ecmascript">/*import math.big |
|||
fn main() { |
|||
//var bb, ptn, etn, dtn big.Int |
|||
pt := "Rosetta Code" |
|||
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 := big.integer_from_string("9516311845790656153499716760847001433441357")? |
|||
e := big.integer_from_string("65537")? |
|||
d := big.integer_from_string("5617843187844953170308463622230283376298685")? |
|||
mut ptn := big.zero_int |
|||
// convert plain text to a number |
|||
for b in pt.bytes() { |
|||
bb := big.integer_from_i64(i64(b)) |
|||
ptn = ptn.lshift(8).bitwise_or(bb) |
|||
} |
|||
if ptn >= n { |
|||
println("Plain text message too long") |
|||
return |
|||
} |
|||
println("Plain text as a number:$ptn") |
|||
// encode a single number |
|||
etn := ptn.big_mod_pow(e,n) |
|||
println("Encoded: $etn") |
|||
// decode a single number |
|||
mut dtn := etn.big_mod_pow(d,n) |
|||
println("Decoded: $dtn") |
|||
// convert number to text |
|||
mut db := [16]u8{} |
|||
mut dx := 16 |
|||
bff := big.integer_from_int(0xff) |
|||
for dtn.bit_len() > 0 { |
|||
dx-- |
|||
bb := dtn.bitwise_and(bff) |
|||
db[dx] = u8(i64(bb.int())) |
|||
dtn = dtn.rshift(8) |
|||
println('${db[0..].bytestr()} ${dtn.bit_len()}') |
|||
} |
|||
println("Decoded number as text: ${db[dx..].bytestr()}") |
|||
}*/ |
|||
import math.big |
|||
blocks = Label(frame, width = 100) |
|||
fn main() { |
|||
blocks.grid(row = 1, column =0) |
|||
//var bb, ptn, etn, dtn big.Int |
|||
pt := "Hello World" |
|||
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 := big.integer_from_string("9516311845790656153499716760847001433441357")? |
|||
e := big.integer_from_string("65537")? |
|||
d := big.integer_from_string("5617843187844953170308463622230283376298685")? |
|||
mut ptn := big.zero_int |
|||
// convert plain text to a number |
|||
for b in pt.bytes() { |
|||
bb := big.integer_from_i64(i64(b)) |
|||
ptn = ptn.lshift(8).bitwise_or(bb) |
|||
} |
|||
if ptn >= n { |
|||
println("Plain text message too long") |
|||
return |
|||
} |
|||
println("Plain text as a number:$ptn") |
|||
// encode a single number |
|||
etn := ptn.big_mod_pow(e,n) |
|||
println("Encoded: $etn") |
|||
// decode a single number |
|||
mut dtn := etn.big_mod_pow(d,n) |
|||
println("Decoded: $dtn") |
|||
// convert number to text |
|||
mut db := [16]u8{} |
|||
mut dx := 16 |
|||
bff := big.integer_from_int(0xff) |
|||
for dtn.bit_len() > 0 { |
|||
dx-- |
|||
bb := dtn.bitwise_and(bff) |
|||
db[dx] = u8(i64(bb.int())) |
|||
dtn = dtn.rshift(8) |
|||
} |
|||
println("Decoded number as text: ${db[dx..].bytestr()}") |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
self.block = StringVar() |
|||
<pre> |
|||
self.block.set("number of blocks") |
|||
Plain text: Hello World |
|||
blocks["textvar"] = self.block |
|||
Plain text as a number:87521618088882533792115812 |
|||
Encoded: 8455179966388263657372423602482472996174613 |
|||
output = Entry(frame, width = 100) |
|||
Decoded: 87521618088882533792115812 |
|||
output.grid(row = 2, column = 0) |
|||
Decoded number as text: Hello World |
|||
</pre> |
|||
=={{header|Wren}}== |
|||
self.answer = StringVar() |
|||
{{trans|Go}} |
|||
self.answer.set("Ciphertext") |
|||
{{libheader|Wren-big}} |
|||
output["textvar"] = self.answer |
|||
<syntaxhighlight lang="wren">import "./big" for BigInt |
|||
var pt = "Rosetta Code" |
|||
# The commands of all the buttons are defined below |
|||
System.print("Plain text: : %(pt)") |
|||
def set_n(self,event): |
|||
var n = BigInt.new("9516311845790656153499716760847001433441357") |
|||
global n |
|||
var e = BigInt.new("65537") |
|||
n = int(self.n.get()) |
|||
var d = BigInt.new("5617843187844953170308463622230283376298685") |
|||
print("n set to", n) |
|||
var ptn = BigInt.zero |
|||
// convert plain text to a number |
|||
for (b in pt.bytes) { |
|||
ptn = (ptn << 8) | BigInt.new(b) |
|||
} |
|||
if (ptn >= n) { |
|||
System.print("Plain text message too long") |
|||
return |
|||
} |
|||
System.print("Plain text as a number : %(ptn)") |
|||
// encode a single number |
|||
def set_e(self, event): |
|||
var etn = ptn.modPow(e, n) |
|||
global e |
|||
System.print("Encoded : %(etn)") |
|||
print("e set to",e) |
|||
// decode a single number |
|||
def set_d(self,event): |
|||
var dtn = etn.modPow(d, n) |
|||
global d |
|||
System.print("Decoded : %(dtn)") |
|||
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 |
|||
// convert number to text |
|||
var db = List.filled(16, 0) |
|||
def Encrypt(self): |
|||
var dx = 16 |
|||
#encrypts a plaintext message using the current key |
|||
var bff = BigInt.new(255) |
|||
global plaintext,numP,q,j,z,X,C |
|||
while (dtn.bitLength > 0) { |
|||
plaintext = self.contents.get() #pulls the plaintext out of the entry box for use |
|||
dx = dx - 1 |
|||
plaintext = plaintext.lower() #places all plaintext in lower case |
|||
db[dx] = (dtn & bff).toSmall |
|||
dtn = dtn >> 8 |
|||
for i in range(len(plaintext)): # converts letters and symbols to their numerical values |
|||
} |
|||
for j in range(len(letter)): |
|||
var s = "" |
|||
if plaintext[i] == letter[j]: |
|||
for (i in dx..15) s = s + String.fromByte(db[i]) |
|||
System.print("Decoded number as text : %(s)")</syntaxhighlight> |
|||
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 |
|||
{{out}} |
|||
<pre> |
|||
Plain text: : Rosetta Code |
|||
Plain text as a number : 25512506514985639724585018469 |
|||
Encoded : 916709442744356653386978770799029131264344 |
|||
Decoded : 25512506514985639724585018469 |
|||
Decoded number as text : Rosetta Code |
|||
</pre> |
|||
=={{header|zkl}}== |
|||
root = Tk() |
|||
{{trans|C}} |
|||
{{libheader|GMP}} |
|||
No blocking. |
|||
<syntaxhighlight lang="zkl">var BN=Import.lib("zklBigNum"); |
|||
n:=BN("9516311845790656153499716760847001433441357"); |
|||
app = App(root) |
|||
e:=BN("65537"); |
|||
d:=BN("5617843187844953170308463622230283376298685"); |
|||
const plaintext="Rossetta Code"; |
|||
root.mainloop() |
|||
pt:=BN(Data(Int,0,plaintext)); // convert string (as stream of bytes) to big int |
|||
root.destroy() |
|||
if(pt>n) throw(Exception.ValueError("Message is too large")); |
|||
</lang> |
|||
println("Plain text: ",plaintext); |
|||
println("As Int: ",pt); |
|||
ct:=pt.powm(e,n); println("Encoded: ",ct); |
|||
pt =ct.powm(d,n); println("Decoded: ",pt); |
|||
txt:=pt.toData().text; // convert big int to bytes, treat as string |
|||
println("As String: ",txt);</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
Plain text: Rossetta Code |
|||
As Int: 6531201733672758787904906421349 |
|||
Encoded: 5278143020249600501803788468419399384934220 |
|||
Decoded: 6531201733672758787904906421349 |
|||
As String: Rossetta Code |
|||
</pre> |
Latest revision as of 19:53, 3 February 2024
You are encouraged to solve this task according to the task description, using any language you may know.
Given an RSA key (n,e,d), construct a program to encrypt and decrypt plaintext messages strings.
Background
RSA code is used to encode secret messages. It is named after Ron Rivest, Adi Shamir, and Leonard Adleman who published it at MIT in 1977. The advantage of this type of encryption is that you can distribute the number “” and “” (which makes up the Public Key used for encryption) to everyone. The Private Key used for decryption “” is kept secret, so that only the recipient can read the encrypted plaintext.
The process by which this is done is that a message, for example “Hello World” is encoded as numbers (This could be encoding as ASCII or as a subset of characters ). This yields a string of numbers, generally referred to as "numerical plaintext", “”. For example, “Hello World” encoded with a=1,...,z=26 by hundreds would yield .
The plaintext must also be split into blocks so that the numerical plaintext is smaller than otherwise 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
The security of the code is based on the secrecy of the Private Key (decryption exponent) “” and the difficulty in factoring “”. Research into RSA facilitated advances in factoring and a number of factoring challenges. Keys of 829 bits have been successfully factored, and NIST now recommends 2048 bit keys going forward (see Asymmetric algorithm key lengths).
Summary of the task requirements:
- Encrypt and Decrypt a short message or two using RSA with a demonstration key.
- Implement RSA do not call a library.
- Encode and decode the message using any reversible method of your choice (ASCII or a=1,..,z=26 are equally fine).
- Either support blocking or give an error if the message would require blocking)
- Demonstrate that your solution could support real keys by using a non-trivial key that requires large integer support (built-in or libraries). There is no need to include library code but it must be referenced unless it is built into the language. The following keys will be meet this requirement;however, they are NOT long enough to be considered secure:
- n = 9516311845790656153499716760847001433441357
- e = 65537
- d = 5617843187844953170308463622230283376298685
- Messages can be hard-coded into the program, there is no need for elaborate input coding.
- Demonstrate that your implementation works by showing plaintext, intermediate results, encrypted text, and decrypted text.
11l
V n = BigInt(‘9516311845790656153499716760847001433441357’)
V e = BigInt(65537)
V d = BigInt(‘5617843187844953170308463622230283376298685’)
V txt = ‘Rosetta Code’
print(‘Plain text: ’txt)
V txtN = txt.reduce(BigInt(0), (a, b) -> a * 256 + b.code)
print(‘Plain text as a number: ’txtN)
V enc = pow(txtN, e, n)
print(‘Encoded: ’enc)
V dec = pow(enc, d, n)
print(‘Decoded: ’dec)
V decTxt = ‘’
L dec != 0
decTxt ‘’= Char(code' dec % 256)
dec I/= 256
print(‘Decoded number as text: ’reversed(decTxt))
- Output:
Plain text: Rosetta Code Plain text as a number: 25512506514985639724585018469 Encoded: 916709442744356653386978770799029131264344 Decoded: 25512506514985639724585018469 Decoded number as text: Rosetta Code
Ada
The code below uses a thik and a thin binding of gmp.
WITH GMP, GMP.Integers, Ada.Text_IO, GMP.Integers.Aliased_Internal_Value, Interfaces.C;
USE GMP, Gmp.Integers, Ada.Text_IO, Interfaces.C;
PROCEDURE Main IS
FUNCTION "+" (U : Unbounded_Integer) RETURN Mpz_T IS (Aliased_Internal_Value (U));
FUNCTION "+" (S : String) RETURN Unbounded_Integer IS (To_Unbounded_Integer (S));
FUNCTION Image_Cleared (M : Mpz_T) RETURN String IS (Image (To_Unbounded_Integer (M)));
N : Unbounded_Integer := +"9516311845790656153499716760847001433441357";
E : Unbounded_Integer := +"65537";
D : Unbounded_Integer := +"5617843187844953170308463622230283376298685";
Plain_Text : CONSTANT String := "Rosetta Code";
M, M_C, M_D : Mpz_T;
-- We import two C functions from the GMP library which are not in the specs of the gmp package
PROCEDURE Mpz_Import
(Rop : Mpz_T; Count : Size_T; Order : Int; Size : Size_T; Endian : Int;
Nails : Size_T; Op : Char_Array);
PRAGMA Import (C, Mpz_Import, "__gmpz_import");
PROCEDURE Mpz_Export
(Rop : OUT Char_Array; Count : ACCESS Size_T; Order : Int; Size : Size_T;
Endian : Int; Nails : Size_T; Op : Mpz_T);
PRAGMA Import (C, Mpz_Export, "__gmpz_export");
BEGIN
Mpz_Init (M);
Mpz_Init (M_C);
Mpz_Init (M_D);
Mpz_Import (M, Plain_Text'Length + 1, 1, 1, 0, 0, To_C (Plain_Text));
Mpz_Powm (M_C, M, +E, +N);
Mpz_Powm (M_D, M_C, +D, +N);
Put_Line ("Encoded plain text: " & Image_Cleared (M));
DECLARE Decrypted : Char_Array (1 .. Mpz_Sizeinbase (M_C, 256));
BEGIN
Put_Line ("Encryption of this encoding: " & Image_Cleared (M_C));
Mpz_Export (Decrypted, NULL, 1, 1, 0, 0, M_D);
Put_Line ("Decryption of the encoding: " & Image_Cleared (M_D));
Put_Line ("Final decryption: " & To_Ada (Decrypted));
END;
END Main;
- Output:
Encoded plain text: 6531201667836323769493764728064 Encryption of this encoding: 8527003485686414372697775926080309566820293 Decryption of the encoding: 6531201667836323769493764728064 Final decryption: Rosetta Code
ALGOL 68
The code below uses Algol 68 Genie which provides arbitrary precision arithmetic for LONG LONG modes.
COMMENT
First cut. Doesn't yet do blocking and deblocking. Also, as
encryption and decryption are identical operations but for the
reciprocal exponents used, only one has been implemented below.
A later release will address these issues.
COMMENT
BEGIN
PR precision=1000 PR
MODE LLI = LONG LONG INT; CO For brevity CO
PROC mod power = (LLI base, exponent, modulus) LLI :
BEGIN
LLI result := 1, b := base, e := exponent;
IF exponent < 0
THEN
put (stand error, (("Negative exponent", exponent, newline)))
ELSE
WHILE e > 0
DO
(ODD e | result := (result * b) MOD modulus);
e OVERAB 2; b := (b * b) MOD modulus
OD
FI;
result
END;
PROC modular inverse = (LLI a, m) LLI :
BEGIN
PROC extended gcd = (LLI x, y) []LLI :
BEGIN
LLI v := 1, a := 1, u := 0, b := 0, g := x, w := y;
WHILE w>0
DO
LLI q := g % w, t := a - q * u;
a := u; u := t;
t := b - q * v;
b := v; v := t;
t := g - q * w;
g := w; w := t
OD;
a PLUSAB (a < 0 | u | 0);
(a, b, g)
END;
[] LLI egcd = extended gcd (a, m);
(egcd[3] > 1 | 0 | egcd[1] MOD m)
END;
PROC number to string = (LLI number) STRING :
BEGIN
[] CHAR map = (blank + "ABCDEFGHIJKLMNOPQRSTUVWXYZ")[@0];
LLI local number := number;
INT length := SHORTEN SHORTEN ENTIER long long log(number) + 1;
(ODD length | length PLUSAB 1);
[length % 2] CHAR text;
FOR i FROM length % 2 BY -1 TO 1
DO
INT index = SHORTEN SHORTEN (local number MOD 100);
text[i] := (index > 26 | "?" | map[index]);
local number := local number % 100
OD;
text
END;
CO The parameters of a particular RSA cryptosystem CO
LLI p = 3490529510847650949147849619903898133417764638493387843990820577;
LLI q = 32769132993266709549961988190834461413177642967992942539798288533;
LLI n = p * q;
LLI phi n = (p-1) * (q-1);
LLI e = 9007;
LLI d = modular inverse (e, phi n);
CO A ciphertext CO
LLI cipher text = 96869613754622061477140922254355882905759991124574319874695120930816298225145708356931476622883989628013391990551829945157815154;
CO Print out the corresponding plain text CO
print (number to string (mod power (ciphertext, d, n)))
END
- Output:
THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gmp.h>
int main(void)
{
mpz_t n, d, e, pt, ct;
mpz_init(pt);
mpz_init(ct);
mpz_init_set_str(n, "9516311845790656153499716760847001433441357", 10);
mpz_init_set_str(e, "65537", 10);
mpz_init_set_str(d, "5617843187844953170308463622230283376298685", 10);
const char *plaintext = "Rossetta Code";
mpz_import(pt, strlen(plaintext), 1, 1, 0, 0, plaintext);
if (mpz_cmp(pt, n) > 0)
abort();
mpz_powm(ct, pt, e, n);
gmp_printf("Encoded: %Zd\n", ct);
mpz_powm(pt, ct, d, n);
gmp_printf("Decoded: %Zd\n", pt);
char buffer[64];
mpz_export(buffer, NULL, 1, 1, 0, 0, pt);
printf("As String: %s\n", buffer);
mpz_clears(pt, ct, n, e, d, NULL);
return 0;
}
- Output:
Encoded: 5278143020249600501803788468419399384934220 Decoded: 6531201733672758787904906421349 As String: Rossetta Code
C#
using System;
using System.Numerics;
using System.Text;
class Program
{
static void Main(string[] args)
{
BigInteger n = BigInteger.Parse("9516311845790656153499716760847001433441357");
BigInteger e = 65537;
BigInteger d = BigInteger.Parse("5617843187844953170308463622230283376298685");
const string plaintextstring = "Hello, Rosetta!";
byte[] plaintext = ASCIIEncoding.ASCII.GetBytes(plaintextstring);
BigInteger pt = new BigInteger(plaintext);
if (pt > n)
throw new Exception();
BigInteger ct = BigInteger.ModPow(pt, e, n);
Console.WriteLine("Encoded: " + ct);
BigInteger dc = BigInteger.ModPow(ct, d, n);
Console.WriteLine("Decoded: " + dc);
string decoded = ASCIIEncoding.ASCII.GetString(dc.ToByteArray());
Console.WriteLine("As ASCII: " + decoded);
}
}
- Output:
Encoded: 8545729659809274764853392532557102329563535 Decoded: 173322416552962951144796590453843272 As ASCII: Hello, Rosetta!
Common Lisp
In this example, the functions encode-string and decode-string are responsible for converting the string to an integer (which can be encoded) and back. They are not very important to the RSA algorithm, which happens in encode-rsa, decode-rsa, and mod-exp.
The string is encoded as follows: each character is converted into 2 digits based on ASCII value (subtracting 32, so that SPACE=00, and so on.) To decode we simply read every 2 digits from the given integer in order, adding 32 and converting back into characters.
(defparameter *n* 9516311845790656153499716760847001433441357)
(defparameter *e* 65537)
(defparameter *d* 5617843187844953170308463622230283376298685)
;; magic
(defun encode-string (message)
(parse-integer (reduce #'(lambda (x y) (concatenate 'string x y))
(loop for c across message collect (format nil "~2,'0d" (- (char-code c) 32))))))
;; sorcery
(defun decode-string (message) (coerce (loop for (a b) on
(loop for char across (write-to-string message) collect char)
by #'cddr collect (code-char (+ (parse-integer (coerce (list a b) 'string)) 32))) 'string))
;; ACTUAL RSA ALGORITHM STARTS HERE ;;
;; fast modular exponentiation: runs in O(log exponent)
;; acc is initially 1 and contains the result by the end
(defun mod-exp (base exponent modulus acc)
(if (= exponent 0) acc
(mod-exp (mod (* base base) modulus) (ash exponent -1) modulus
(if (= (mod exponent 2) 1) (mod (* acc base) modulus) acc))))
;; to encode a message, we first convert it to its integer form.
;; then, we raise it to the *e* power, modulo *n*
(defun encode-rsa (message)
(mod-exp (encode-string message) *e* *n* 1))
;; to decode a message, we raise it to *d* power, modulo *n*
;; and then convert it back into a string
(defun decode-rsa (message)
(decode-string (mod-exp message *d* *n* 1)))
Interpreter output (the star * represents the interpreter prompt):
* (load "rsa.lisp") T * (encode-rsa "Rosetta Code") 4330737636866106722999010287941987299297557 * (decode-rsa 4330737636866106722999010287941987299297557) "Rosetta Code"
D
This used the D module of the Modular Exponentiation Task.
void main() {
import std.stdio, std.bigint, std.algorithm, std.string, std.range,
modular_exponentiation;
immutable txt = "Rosetta Code";
writeln("Plain text: ", txt);
// 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.
immutable BigInt n = "2463574872878749457479".BigInt *
"3862806018422572001483".BigInt;
immutable BigInt e = 2 ^^ 16 + 1;
immutable BigInt d = "5617843187844953170308463622230283376298685";
// Convert plain text to a number.
immutable txtN = reduce!q{ (a << 8) | uint(b) }(0.BigInt, txt);
if (txtN >= n)
return writeln("Plain text message too long.");
writeln("Plain text as a number: ", txtN);
// Encode a single number.
immutable enc = txtN.powMod(e, n);
writeln("Encoded: ", enc);
// Decode a single number.
auto dec = enc.powMod(d, n);
writeln("Decoded: ", dec);
// Convert number to text.
char[] decTxt;
for (; dec; dec >>= 8)
decTxt ~= (dec & 0xff).toInt;
writeln("Decoded number as text: ", decTxt.retro);
}
- Output:
Plain text: Rosetta Code Plain text as a number: 25512506514985639724585018469 Encoded: 916709442744356653386978770799029131264344 Decoded: 25512506514985639724585018469 Decoded number as text: Rosetta Code
Delphi
Thanks for Rudy Velthuis, BigIntegers library
program RSA_code;
{$APPTYPE CONSOLE}
uses
System.SysUtils,
Velthuis.BigIntegers;
type
TRSA = record
private
n, e, d: BigInteger;
class function PlainTextAsNumber(data: AnsiString): BigInteger; static;
class function NumberAsPlainText(Num: BigInteger): AnsiString; static;
public
constructor Create(n, e, d: string);
function Encode(data: AnsiString): string;
function Decode(code: string): AnsiString;
end;
function EncodeRSA(data: AnsiString): string;
var
n, e, d, bb, ptn, etn, dtn: BigInteger;
begin
// 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 := '9516311845790656153499716760847001433441357';
e := '65537';
d := '5617843187844953170308463622230283376298685';
for var c in data do
begin
bb := ord(c);
ptn := (ptn shl 8) or bb;
end;
if BigInteger.Compare(ptn, n) >= 0 then
begin
Writeln('Plain text message too long');
exit;
end;
writeln('Plain text as a number:', ptn.ToString);
writeln(ptn.ToString);
// encode a single number
etn := BigInteger.ModPow(ptn, e, n);
Writeln('Encoded: ', etn.ToString);
// decode a single number
dtn := BigInteger.ModPow(etn, d, n);
Writeln('Decoded: ', dtn.ToString);
// convert number to text
var db: AnsiString;
var bff: BigInteger := $FF;
while dtn.BitLength > 0 do
begin
db := ansichar((dtn and bff).AsInteger) + db;
dtn := dtn shr 8;
end;
Write('Decoded number as text:"', db, '"');
end;
const
pt = 'Rosetta Code';
{ TRSA }
constructor TRSA.Create(n, e, d: string);
begin
self.n := n;
self.e := e;
self.d := d;
end;
function TRSA.Decode(code: string): AnsiString;
var
etn, dtn: BigInteger;
begin
// decode a single number
etn := code;
dtn := BigInteger.ModPow(etn, d, n);
Result := NumberAsPlainText(dtn);
end;
function TRSA.Encode(data: AnsiString): string;
var
ptn: BigInteger;
begin
ptn := PlainTextAsNumber(data);
// encode a single number
Result := BigInteger.ModPow(ptn, e, n).ToString;
end;
class function TRSA.NumberAsPlainText(Num: BigInteger): AnsiString;
var
bff: BigInteger;
begin
// convert number to text
bff := $FF;
Result := '';
while Num.BitLength > 0 do
begin
Result := ansichar((Num and bff).AsInteger) + Result;
Num := Num shr 8;
end;
end;
class function TRSA.PlainTextAsNumber(data: AnsiString): BigInteger;
var
c: AnsiChar;
bb, n: BigInteger;
begin
Result := 0;
n := '9516311845790656153499716760847001433441357';
for c in data do
begin
bb := ord(c);
Result := (Result shl 8) or bb;
end;
if BigInteger.Compare(Result, n) >= 0 then
raise Exception.Create('Plain text message too long');
end;
var
RSA: TRSA;
Encoded: string;
const
n = '9516311845790656153499716760847001433441357';
e = '65537';
d = '5617843187844953170308463622230283376298685';
TEST_WORD = 'Rosetta Code';
begin
RSA := TRSA.Create(n, e, d);
Encoded := RSA.Encode(TEST_WORD);
writeln('Plain text: ', TEST_WORD);
writeln('Encoded: ', Encoded);
writeln('Decoded: ', RSA.Decode(Encoded));
Readln;
end.
- Output:
Plain text: Rosetta Code Encoded: 916709442744356653386978770799029131264344 Decoded: Rosetta Code
Erlang
Solution split into 2 modules, the mod module does the modulo aritmetic as per separate Rosetta Code entry.
%%% @author Tony Wallace <tony@tony.gen.nz>
%%% @doc
%%% For details of the algorithms used see
%%% https://en.wikipedia.org/wiki/Modular_exponentiation
%%% @end
%%% Created : 21 Jul 2021 by Tony Wallace <tony@resurrection>
-module mod.
-export [mod_mult/3,mod_exp/3,binary_exp/2,test/0].
mod_mult(I1,I2,Mod) when
I1 > Mod,
is_integer(I1), is_integer(I2), is_integer(Mod) ->
mod_mult(I1 rem Mod,I2,Mod);
mod_mult(I1,I2,Mod) when
I2 > Mod,
is_integer(I1), is_integer(I2), is_integer(Mod) ->
mod_mult(I1,I2 rem Mod,Mod);
mod_mult(I1,I2,Mod) when
is_integer(I1), is_integer(I2), is_integer(Mod) ->
(I1 * I2) rem Mod.
mod_exp(Base,Exp,Mod) when
is_integer(Base),
is_integer(Exp),
is_integer(Mod),
Base > 0,
Exp > 0,
Mod > 0 ->
binary_exp_mod(Base,Exp,Mod);
mod_exp(_,0,_) -> 1.
binary_exp(Base,Exponent) when
is_integer(Base),
is_integer(Exponent),
Base > 0,
Exponent > 0 ->
binary_exp(Base,Exponent,1);
binary_exp(_,0) ->
1.
binary_exp(_,0,Result) ->
Result;
binary_exp(Base,Exponent,Acc) ->
binary_exp(Base*Base,Exponent bsr 1,Acc * exp_factor(Base,Exponent)).
binary_exp_mod(Base,Exponent,Mod) ->
binary_exp_mod(Base rem Mod,Exponent,Mod,1).
binary_exp_mod(_,0,_,Result) ->
Result;
binary_exp_mod(Base,Exponent,Mod,Acc) ->
binary_exp_mod((Base*Base) rem Mod,
Exponent bsr 1,Mod,(Acc * exp_factor(Base,Exponent))rem Mod).
exp_factor(_,0) ->
1;
exp_factor(Base,1) ->
Base;
exp_factor(Base,Exponent) ->
exp_factor(Base,Exponent band 1).
test() ->
445 = mod_exp(4,13,497),
%% Rosetta code example:
R = 1527229998585248450016808958343740453059 =
mod_exp(2988348162058574136915891421498819466320163312926952423791023078876139,
2351399303373464486466122544523690094744975233415544072992656881240319,
binary_exp(10,40)),
R.
%%%-------------------------------------------------------------------
%%% @author Tony Wallace <tony@tony.gen.nz>
%%% @doc
%%% Blocking not implemented. Runtime exception if message too long
%%% Not a practical issue as RSA usually limited to symmetric key exchange
%%% However as a key exchange tool no advantage in compressing plaintext
%%% so that is not done either.
%%% @end
%%% Created : 24 Jul 2021 by Tony Wallace <tony@resurrection>
%%%-------------------------------------------------------------------
-module rsa.
-export([key_gen/2,encrypt/2,decrypt/2,test/0]).
-type key() :: {integer(),integer()}.
key_gen({N,D},E) ->
{{E,N},{D,N}}.
-spec encrypt(key(),integer()) -> integer().
encrypt({E,N},MessageInt)
when MessageInt < N ->
mod:mod_exp(MessageInt,E,N).
-spec decrypt(key(),integer()) -> integer().
decrypt({D,N},Message) ->
mod:mod_exp(Message,D,N).
test() ->
PlainText=10722935,
N = 9516311845790656153499716760847001433441357,
E = 65537,
D = 5617843187844953170308463622230283376298685,
{PublicKey,PrivateKey} = key_gen({N,D},E),
PlainText =:= decrypt(PrivateKey,
encrypt(PublicKey,PlainText)).
Running test: 8> rsa:test(). rsa:test(). true 9>
F#
//Nigel Galloway February 12th., 2018
let RSA n g l = bigint.ModPow(l,n,g)
let encrypt = RSA 65537I 9516311845790656153499716760847001433441357I
let m_in = System.Text.Encoding.ASCII.GetBytes "The magic words are SQUEAMISH OSSIFRAGE"|>Array.chunkBySize 16|>Array.map(Array.fold(fun n g ->(n*256I)+(bigint(int g))) 0I)
let n = Array.map encrypt m_in
let decrypt = RSA 5617843187844953170308463622230283376298685I 9516311845790656153499716760847001433441357I
let g = Array.map decrypt n
let m_out = Array.collect(fun n->Array.unfold(fun n->if n>0I then Some(byte(int (n%256I)),n/256I) else None) n|>Array.rev) g|>System.Text.Encoding.ASCII.GetString
printfn "'The magic words are SQUEAMISH OSSIFRAGE' as numbers -> %A\nEncrypted -> %A\nDecrypted -> %A\nAs text -> %A" m_in n g m_out
- Output:
'The magic words are SQUEAMISH OSSIFRAGE' as numbers -> [|112197201611743344895286521511035564832; 129529088517466560781735691575334293331; 23442989443532613|] Encrypted -> [|3493129515654757560886946157927565680562316; 5582490186309277335090560762784439391588703; 8700785834706594190338047528968122486721264|] Decrypted -> [|112197201611743344895286521511035564832; 129529088517466560781735691575334293331; 23442989443532613|] As text -> "The magic words are SQUEAMISH OSSIFRAGE"
FreeBASIC
' version 17-01-2017
' compile with: fbc -s console
#Include Once "gmp.bi"
Dim As Mpz_ptr e, d, n, pt, ct
e = Allocate(Len(__mpz_struct))
d = Allocate(Len(__mpz_struct))
n = Allocate(Len(__mpz_struct))
pt = Allocate(Len(__mpz_struct)) : mpz_init(pt)
ct = Allocate(Len(__mpz_struct)) : mpz_init(ct)
mpz_init_set_str(e, "65537", 10)
mpz_init_set_str(d, "5617843187844953170308463622230283376298685", 10)
mpz_init_set_str(n, "9516311845790656153499716760847001433441357", 10)
Dim As ZString Ptr plaintext : plaintext = Allocate(1000)
Dim As ZString Ptr text : text = Allocate(1000)
*plaintext = "Rosetta Code"
mpz_import(pt, Len(*plaintext), 1, 1, 0, 0, plaintext)
If mpz_cmp(pt, n) > 0 Then GoTo clean_up
mpz_powm(ct, pt, e, n)
gmp_printf(!" Encoded: %Zd\n", ct)
mpz_powm(pt, ct, d, n)
gmp_printf(!" Decoded: %Zd\n", pt)
mpz_export(text, NULL, 1, 1, 0, 0, pt)
Print "As string: "; *text
clean_up:
DeAllocate(plaintext) : DeAllocate(text)
mpz_clear(e) : mpz_clear(d) : mpz_clear(n)
mpz_clear(pt) : mpz_clear(ct)
' empty keyboard buffer
While Inkey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End
- Output:
Encoded: 916709442744356653386978770799029131264344 Decoded: 25512506514985639724585018469 As string: Rosetta Code
Go
Note: see the crypto/rsa package included with Go for a full implementation.
package main
import (
"fmt"
"math/big"
)
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)))
}
if ptn.Cmp(&n) >= 0 {
fmt.Println("Plain text message too long")
return
}
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:]))
}
Output:
Plain text: Rosetta Code Plain text as a number: 25512506514985639724585018469 Encoded: 916709442744356653386978770799029131264344 Decoded: 25512506514985639724585018469 Decoded number as text: Rosetta Code
Haskell
module RSAMaker
where
import Data.Char ( chr )
encode :: String -> [Integer]
encode s = map (toInteger . fromEnum ) s
rsa_encode :: Integer -> Integer -> [Integer] -> [Integer]
rsa_encode n e numbers = map (\num -> mod ( num ^ e ) n ) numbers
rsa_decode :: Integer -> Integer -> [Integer] -> [Integer]
rsa_decode d n ciphers = map (\c -> mod ( c ^ d ) n ) ciphers
decode :: [Integer] -> String
decode encoded = map ( chr . fromInteger ) encoded
divisors :: Integer -> [Integer]
divisors n = [m | m <- [1..n] , mod n m == 0 ]
isPrime :: Integer -> Bool
isPrime n = divisors n == [1,n]
totient :: Integer -> Integer -> Integer
totient prime1 prime2 = (prime1 - 1 ) * ( prime2 - 1 )
myE :: Integer -> Integer
myE tot = head [n | n <- [2..tot - 1] , gcd n tot == 1]
myD :: Integer -> Integer -> Integer -> Integer
myD e n phi = head [d | d <- [1..n] , mod ( d * e ) phi == 1]
main = do
putStrLn "Enter a test text!"
text <- getLine
let primes = take 90 $ filter isPrime [1..]
p1 = last primes
p2 = last $ init primes
tot = totient p1 p2
e = myE tot
n = p1 * p2
rsa_encoded = rsa_encode n e $ encode text
d = myD e n tot
encrypted = concatMap show rsa_encoded
decrypted = decode $ rsa_decode d n rsa_encoded
putStrLn ("Encrypted: " ++ encrypted )
putStrLn ("And now decrypted: " ++ decrypted )
- Output:
Enter a test text! Rosettacode Encrypted: 65646265111107071564791028551028551458331139502651145035156479 And now decrypted: Rosettacode
Icon and Unicon
Please read talk pages.
Output:
RSA Demo using n = 9516311845790656153499716760847001433441357 e = 65537 d = 5617843187844953170308463622230283376298685 b = 5575186299632655785383929568162090376495104 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 = "This message is too long." Encoded = 529836718428469753460978059376661024804668788418205881100078 Encrypt = 3376966937987363040878203966915676619521252 7002174816151673360605669161609885530980579 Decrypt = 95034800624219541 4481988526688939374478063610382714873472814 Unblocked = 529836718428469753460978059376661024804668788418205881100078 Decoded = "This message is too long." Message = "xxxxxxxxxxxxxxxxxx" Encoded = 10494468328720293243075632128305111296931960 Encrypt = 1 829820657892505002815717051746917810425013 Decrypt = 1 4919282029087637457691702560143020920436856 Unblocked = 10494468328720293243075632128305111296931960 Decoded = "xxxxxxxxxxxxxxxxxx"
J
Note, for an implementation with blocking (and a much smaller key) see [1]
N=: 9516311845790656153499716760847001433441357x
E=: 65537x
D=: 5617843187844953170308463622230283376298685x
] text=: 'Rosetta Code'
Rosetta Code
] num=: 256x #. a.i.text
25512506514985639724585018469
num >: N NB. check if blocking is necessary (0 means no)
0
] enc=: N&|@^&E num
916709442744356653386978770799029131264344
] dec=: N&|@^&D enc
25512506514985639724585018469
] final=: a. {~ 256x #.inv dec
Rosetta Code
Note: as indicated at http://www.jsoftware.com/help/dictionary/special.htm, N&|@^
does not bother with creating the exponential intermediate result.
Java
public static void main(String[] args) {
/*
This is probably not the best method...or even the most optimized way...however it works since n and d are too big to be ints or longs
This was also only tested with 'Rosetta Code' and 'Hello World'
It's also pretty limited on plainText size (anything bigger than the above will fail)
*/
BigInteger n = new BigInteger("9516311845790656153499716760847001433441357");
BigInteger e = new BigInteger("65537");
BigInteger d = new BigInteger("5617843187844953170308463622230283376298685");
Charset c = Charsets.UTF_8;
String plainText = "Rosetta Code";
System.out.println("PlainText : " + plainText);
byte[] bytes = plainText.getBytes();
BigInteger plainNum = new BigInteger(bytes);
System.out.println("As number : " + plainNum);
BigInteger Bytes = new BigInteger(bytes);
if (Bytes.compareTo(n) == 1) {
System.out.println("Plaintext is too long");
return;
}
BigInteger enc = plainNum.modPow(e, n);
System.out.println("Encoded: " + enc);
BigInteger dec = enc.modPow(d, n);
System.out.println("Decoded: " + dec);
String decText = new String(dec.toByteArray(), c);
System.out.println("As text: " + decText);
}
Alternative solution - convert to byte array then to BigInteger:
import java.math.BigInteger;
import java.util.Random;
public class rsaCode {
public static void main(String[]args){
//Size of primes
int BIT_LENGTH = 4096;
Random rand = new Random();
//Generate primes and other necessary values
BigInteger p = BigInteger.probablePrime(BIT_LENGTH / 2, rand);
BigInteger q = BigInteger.probablePrime(BIT_LENGTH / 2, rand);
BigInteger n = p.multiply(q);
BigInteger phi = p.subtract(BigInteger.valueOf(1)).multiply(q.subtract(BigInteger.valueOf(1)));
BigInteger e;
BigInteger d;
do {
e = new BigInteger(phi.bitLength(), rand);
} while (e.compareTo(BigInteger.valueOf(1)) <= 0 || e.compareTo(phi) >= 0 || !e.gcd(phi).equals(BigInteger.valueOf(1)));
d = e.modInverse(phi);
//Convert message to byte array and then to a BigInteger
BigInteger message = new BigInteger("Hello World! - From Rosetta Code".getBytes());
BigInteger cipherText = message.modPow(e, n);
BigInteger decryptedText = cipherText.modPow(d, n);
System.out.println("Message: " + message);
System.out.println("Prime 1: " + p);
System.out.println("Prime 2: " + q);
System.out.println("Phi p1 * p2: " + phi);
System.out.println("p1 * p2: " + n);
System.out.println("Public key: " + e);
System.out.println("Private key: " + d);
System.out.println("Ciphertext: " + cipherText);
System.out.println("Decrypted message(number form): " + decryptedText);
//Convert BigInteger to byte array then to String
System.out.println("Decrypted message(string): " + new String(decryptedText.toByteArray()));
}
}
- Output:
Message: 32745724963520459128167607565116331713761641910444445962992228853365120918629 Prime 1: 19236082984974163990952162748173714068049389803543876908591023542434008581726901827775282361343539027357627272183474081300821830594665417249999421476471444612045376319151307819458083226682409477411524022807762467877933511178646356355356721278159329226472299570078614830307335816363768128995044913560110586093645150502887099142708810425659608200567299323058631080348801201371891024721397456687923823598994147721120698707559677560198153919129668778208924015134166710369131053236474139106999881687335966483688956493993503452781613364724067448118712996621139377805320411264206346354690147839668674568385780953439324061827 Prime 2: 17979329033868078796981009025342087899891110883452413861085335446537232859657584956199529432436753743100057017453176958641563538906032576785591580481524960405796753482749211728790206586594224271803757384485305551705171358489679998051039658612346599741622638134691446099105450988669667758655426868708523266671158484337114750111466361420411180131539156350206088712722069263680478398363920580976741655559629459204726096055804150577131670026585406567505359058210528861172448235138919989250928848721850118962177309953951127503325970279819172102106621073790956566530104217789478786634899278802600883073967446382373644250257 Phi p1 * p2: 345851865309641725173652598401242058900566653910908938475312921380066114219124630361012048649340940349701681628058518630535276222954695692233147670047674008455691941733381178283159719985229687501019788350058464636500196522521346408404768715926660411771389935137989577763538670548607053837834611583177259789432946335846775973340201166384784256821490809726897985505537384164828673170953111807028144501567927080933277305734847328999516054393161305269105612852357562678721346577533872335946654435942111678921979428611842390495534195723208415846942969477148117377158823876687230703157218761840307200229212313941422321195051355226377851222163854147510935258095666300221082823130614374400292194084084333352100386386600651725502133645428505729406848959785973133150969119775159790464605612595258587741654065352840099419921194642121733262659814580729725479879031162109276830902575494117198577188807279359692336933181285455336126206772237317229756148090589146421446485136412385682723586947367965091078676401379642267664924847358476052429919297388821038943132363371365451994109675932621652038431036384121653367832798502022879709943736316295610602665722391298109723459179009548775436875778616030750642493163185541967992915955989097200396360327456 p1 * p2: 345851865309641725173652598401242058900566653910908938475312921380066114219124630361012048649340940349701681628058518630535276222954695692233147670047674008455691941733381178283159719985229687501019788350058464636500196522521346408404768715926660411771389935137989577763538670548607053837834611583177259789432946335846775973340201166384784256821490809726897985505537384164828673170953111807028144501567927080933277305734847328999516054393161305269105612852357562678721346577533872335946654435942111678921979428611842390495534195723208415846942969477148117377158823876687230703157218761840307200229212313941422321195088570638396693464951787319284451060063606800908079113900290733389263435525468820136075198180380944495959817935065156769349234329286671127186560121733156195482447742397159107289902355166116733169136476049414801282242919450398051834285427541999782759870670431821968638118220066164725772820831757237604760059537040952069757997344764318267517273468518841355988306740438835556131045824464960305329590326517099659355766092152184867080462187317080527339823959005966347609972615672497047496190727232432065795389602582743555233621829974942652963009404343619187532820114040659804327626152774968610262473598342324536209328639539 Public key: 193579940416764762032781091221143757801413904551984303885407040026321908965197971867687112770438003048686335467825121571041736775396425178706013366881005246973351188647629560663037810331045292388828497048500842585316962463760854316963245076613682542629780184301654965436793943481122744003077197338402843407520722504896640189710671321124115630104805979401188537742997889316213029383963089439143905748656345056757946693819634971714186428073990059096062771479710217863926284515341443931092854041306087536208153864059633604334787035313177701948799425284530371404018395643074910533253129726213643193854656336232925658951811658248314007700619000559672273590950586652099230800733098520827807590026231300954320448333065980082309254977488081625340716095420728271744505284703847569933308644755417715559811180764086973488668246118187715534944871349843316776293048731714297576612062481854912918664986385922123428018736434561518771685854566894264705876397229699222060976725454055036743075458563364307745597456824543609383372429743649103452964024219143956601668222718087847554469024737873441872945480724976527827721060219946775750776694792509727838512629661637130805269017888622785492890741411798087685393616016451666522802755139926311245306229041 Private key: 219036175169203544315490853999486820834618560996816043411987210664248102884377915567272406198057873662330646577076795355640818453754512006948660586443609679011052139043660581484406998357727395227184641632029033848943507736672039637904589489626534363470520344933214278535075666039716685014892551021861132000517572948046870070641407067319704943583671179776670601874690644590228314092730047599467716558027443683253737751585758991176998516378325292822247842855150355043416320003512453741917219948896684868393696007264717697967091707113384847407621846752255898098912112528872599250195047315005253431619786863325536528182598792588704861531564144935586585480994816595663012912390628905402008731003235520424397350241617043412307761990786711273480686856614955176903059108533627807572077696388568308581773433971401736018773723311485647784158083000913638874130114372027510789163873963163280849749880619112666293979830817843596818936327354256104400652111217685523782967475741729222155996255475772715455781288940265345618022791173798222315117453828105848080873781770073614996444414329484314974671715475986173113744470587849073918357399130907446602201256421236363869748993676713228862789197394591401079130691347928057018496258825068434610372879057 Ciphertext: 751802077965963630324549365263121640277689482825128224616526073196054301029392106215761462171255492597878612184351606323296123153021421277191908278007450520130118453205040455128556435393691729542297181525367763857641211099694558032110059874156910175402903627759175935900055257215548262301358748652386044838566618270488287858766869634274195146217020325014127218881028662056032737660265341221411932659292844178938078127559747544470249139600492686861162904399444542749100026596955221740375230453344396141534329779530430928001439479395156999496805099234924399049952788417632216512939528956109220706809364166228124854558311835437452608371779980805227059349785343399382366770619320980575920634550115026075376299109862825119723058827075167366432962208711425854647134395509013075755502864140908914499073909257771585668395445413050111450415828406012614877021632277223689796818643848597729370856433117827304201297547912764020996146635163811573223631120712910083451904964228318515972103019499763177402019351409722785807448842923761649884358555226283418059099812653679780193380193208207168410802721122329377467373427784070234188000453256581358361888268040964222190110448131244743936030485464773996914221120717918807573232494076059754978713933 Decrypted message(number form): 32745724963520459128167607565116331713761641910444445962992228853365120918629 Decrypted message(string): Hello World! - From Rosetta Code
jq
Adapted from Wren after correcting for a bug in the decode-to-text algorithm as of 2023-02-07
Works with gojq, the Go implementation of jq, and with fq
The following assumes unbounded-precision integer arithmetic.
# If $j is 0, then an error condition is raised;
# otherwise, assuming infinite-precision integer arithmetic,
# if the input and $j are integers, then the result will be an integer.
def idivide($j): (. - (. % $j)) / $j ;
# shift left
def left8: 256 * .;
# shift right
def right8: idivide(256);
def modPow($b; $e; $m):
if ($m == 1) then 0
else {b: ($b % $m), $e, r: 1}
| until( .e <= 0 or .return;
if .b == 0 then .return = 0
else if .e % 2 == 1 then .r = (.r * .b) % $m else . end
| .e |= idivide(2)
| .b = (.b * .b) % $m
end)
| if .return then .return else .r end
end;
# Convert the input integer to a stream of 8-bit integers, most significant first
def bytes:
def stream:
recurse(if . >= 256 then ./256|floor else empty end) | . % 256 ;
[stream] | reverse ;
# convert ASCII plain text to a number
def ptn:
reduce explode[] as $b (0; left8 + $b);
def n: 9516311845790656153499716760847001433441357;
def e: 65537;
def d: 5617843187844953170308463622230283376298685;
# encode a single number
def etn: . as $ptn | modPow($ptn; e; n);
# decode a single number
def dtn: . as $etn | modPow($etn; d; n);
def decode:
[recurse(right8 | select(.>0)) % 256]
| reverse
| implode;
def task($pt):
($pt|ptn) as $ptn
| if ($ptn >= n) then "Plain text message too long" | error else . end
| ($ptn|etn) as $etn
| ($etn|dtn) as $dtn
| ($ptn|decode) as $text
| "Plain text: : \($pt)",
"Plain text as a number : \($ptn)",
"Encoded : \($etn)",
"Decoded : \($dtn)",
"Decoded number as text : \($text)"
;
task("Rosetta Code"),
"",
task("Hello, Rosetta!!!!")
Invocation: gojq -nr -f rsa-code.jq
- Output:
Plain text: : Rosetta Code Plain text as a number : 25512506514985639724585018469 Encoded : 916709442744356653386978770799029131264344 Decoded : 25512506514985639724585018469 Decoded number as text : Rosetta Code Plain text: : Hello, Rosetta!!!! Plain text as a number : 6306597225792201544376884997106189304144161 Encoded : 3763881655974029977658577646869029457590896 Decoded : 6306597225792201544376884997106189304144161 Decoded number as text : Hello, Rosetta!!!!
Julia
function rsaencode(clearmsg::AbstractString, nmod::Integer, expub::Integer)
bytes = parse(BigInt, "0x" * bytes2hex(collect(UInt8, clearmsg)))
return powermod(bytes, expub, nmod)
end
function rsadecode(cryptmsg::Integer, nmod::Integer, dsecr::Integer)
decoded = powermod(encoded, dsecr, nmod)
return join(Char.(hex2bytes(hex(decoded))))
end
msg = "Rosetta Code."
nmod = big"9516311845790656153499716760847001433441357"
expub = 65537
dsecr = big"5617843187844953170308463622230283376298685"
encoded = rsaencode(msg, nmod, expub)
decoded = rsadecode(encoded, nmod, dsecr)
println("\n# $msg\n -> ENCODED: $encoded\n -> DECODED: $decoded")
- Output:
# Rosetta Code. -> ENCODED: 2440331969632134446717000067136916252596373 -> DECODED: Rosetta Code.
Kotlin
// version 1.1.4-3
import java.math.BigInteger
fun main(args: Array<String>) {
val n = BigInteger("9516311845790656153499716760847001433441357")
val e = BigInteger("65537")
val d = BigInteger("5617843187844953170308463622230283376298685")
val c = Charsets.UTF_8
val plainText = "Rosetta Code"
println("PlainText : $plainText")
val bytes = plainText.toByteArray(c)
val plainNum = BigInteger(bytes)
println("As number : $plainNum")
if (plainNum > n) {
println("Plaintext is too long")
return
}
val enc = plainNum.modPow(e, n)
println("Encoded : $enc")
val dec = enc.modPow(d, n)
println("Decoded : $dec")
val decText = dec.toByteArray().toString(c)
println("As text : $decText")
}
- Output:
PlainText : Rosetta Code As number : 25512506514985639724585018469 Encoded : 916709442744356653386978770799029131264344 Decoded : 25512506514985639724585018469 As text : Rosetta Code
Mathematica/Wolfram Language
Does not support blocking.
toNumPlTxt[s_] := FromDigits[ToCharacterCode[s], 256];
fromNumPlTxt[plTxt_] := FromCharacterCode[IntegerDigits[plTxt, 256]];
enc::longmess = "Message '``' is too long for n = ``.";
enc[n_, _, mess_] /;
toNumPlTxt[mess] >= n := (Message[enc::longmess, mess, n]; $Failed);
enc[n_, e_, mess_] := PowerMod[toNumPlTxt[mess], e, n];
dec[n_, d_, en_] := fromNumPlTxt[PowerMod[en, d, n]];
text = "The cake is a lie!";
n = 9516311845790656153499716760847001433441357;
e = 65537;
d = 5617843187844953170308463622230283376298685;
en = enc[n, e, text];
de = dec[n, d, en];
Print["Text: '" <> text <> "'"];
Print["n = " <> IntegerString[n]];
Print["e = " <> IntegerString[e]];
Print["d = " <> IntegerString[d]];
Print["Numeric plaintext: " <> IntegerString[toNumPlTxt[text]]];
Print["Encoded: " <> IntegerString[en]];
Print["Decoded: '" <> de <> "'"];
- Output:
Text: 'The cake is a lie!' n = 9516311845790656153499716760847001433441357 e = 65537 d = 5617843187844953170308463622230283376298685 Numeric plaintext: 7352955804624388987810264523908743852287265 Encoded: 199505409518408949879682159958576932863989 Decoded: 'The cake is a lie!'
Nim
import strutils, streams, strformat
# nimble install stint
import stint
const messages = ["PPAP", "I have a pen, I have a apple\nUh! Apple-pen!",
"I have a pen, I have pineapple\nUh! Pineapple-pen!",
"Apple-pen, pineapple-pen\nUh! Pen-pineapple-apple-pen\nPen-pineapple-apple-pen\nDance time!", "\a\0"]
const
n = u256("9516311845790656153499716760847001433441357")
e = u256("65537")
d = u256("5617843187844953170308463622230283376298685")
proc pcount(s: string, c: char): int{.inline.} =
for ch in s:
if ch != c:
break
result+=1
func powmodHexStr(s: string, key, divisor: UInt256): string{.inline.} =
toHex(powmod(UInt256.fromHex(s), key, divisor))
proc translate(hexString: string, key, divisor: UInt256,
encrypt = true): string =
var
strm = newStringStream(hexString)
chunk, residue, tempChunk: string
let chunkSize = len(toHex(divisor))
while true:
tempChunk = strm.peekStr(chunkSize-int(encrypt)*3)
if len(chunk) > 0:
if len(tempChunk) == 0:
if encrypt:
result&=powmodHexStr(pcount(chunk, '0').toHex(2)&align(chunk,
chunkSize-3, '0'), key, divisor)
else:
tempChunk = align(powmodHexStr(chunk, key, divisor), chunkSize-1, '0')
residue = tempChunk[2..^1].strip(trailing = false, chars = {'0'})
result&=align(residue, fromHex[int](tempChunk[0..1])+len(residue), '0')
break
result&=align(powmodHexStr(chunk, key, divisor), chunkSize-3+int(
encrypt)*3, '0')
discard strm.readStr(chunkSize-int(encrypt)*3)
chunk = tempChunk
strm.close()
for message in messages:
echo(&"plaintext:\n{message}")
var numPlaintext = message.toHex()
echo(&"numerical plaintext in hex:\n{numPlaintext}")
var ciphertext = translate(numPlaintext, e, n)
echo(&"ciphertext is: \n{ciphertext}")
var deciphertext = translate(ciphertext, d, n, false)
echo(&"deciphered numerical plaintext in hex is:\n{deciphertext}")
echo(&"deciphered plaintext is:\n{parseHexStr(deciphertext)}\n\n")
- Output:
plaintext: PPAP numerical plaintext in hex: 50504150 ciphertext is: 6c55b71c718b8921555eaa9754b7bfd7018b deciphered numerical plaintext in hex is: 50504150 deciphered plaintext is: PPAP plaintext: I have a pen, I have a apple Uh! Apple-pen! numerical plaintext in hex: 49206861766520612070656E2C204920686176652061206170706C650A556821204170706C652D70656E21 ciphertext is: 4614caba02ac33654130c10485dcceeec4a2443f4bffb46e389c2705d4ebd7ac7185a206ae0294575f283841baad236fa90d5c5536b deciphered numerical plaintext in hex is: 49206861766520612070656e2c204920686176652061206170706c650a556821204170706c652d70656e21 deciphered plaintext is: I have a pen, I have a apple Uh! Apple-pen! plaintext: I have a pen, I have pineapple Uh! Pineapple-pen! numerical plaintext in hex: 49206861766520612070656E2C204920686176652070696E656170706C650A5568212050696E656170706C652D70656E21 ciphertext is: 4614caba02ac33654130c10485dcceeec4a21c96dd7a5048e412a16c65e274609964ffb14231b9d6a70a59380d4bbaef3c40e88afa3d deciphered numerical plaintext in hex is: 49206861766520612070656e2c204920686176652070696e656170706c650a5568212050696e656170706c652d70656e21 deciphered plaintext is: I have a pen, I have pineapple Uh! Pineapple-pen! plaintext: Apple-pen, pineapple-pen Uh! Pen-pineapple-apple-pen Pen-pineapple-apple-pen Dance time! numerical plaintext in hex: 4170706C652D70656E2C2070696E656170706C652D70656E0A5568212050656E2D70696E656170706C652D6170706C652D70656E0A50656E2D70696E656170706C652D6170706C652D70656E0A44616E63652074696D6521 ciphertext is: 5d733e3979b0b43207dace453c3ec65baaff54571a3127be4ccd120dff94fb2e1b9258d6067cee2669e868ee4390c5e16f61016a171f6585ad4cd58ca3335bc9faa96da943bfedad0dd0ac7cbc83a256bf9f6f65d755865aed232e1e0a467512a6744f3f470ee283c8b4e2e5 deciphered numerical plaintext in hex is: 4170706c652d70656e2c2070696e656170706c652d70656e0a5568212050656e2d70696e656170706c652d6170706c652d70656e0a50656e2d70696e656170706c652d6170706c652d70656e0a44616e63652074696d6521 deciphered plaintext is: Apple-pen, pineapple-pen Uh! Pen-pineapple-apple-pen Pen-pineapple-apple-pen Dance time! plaintext: (shell terminal cannot display "\a\0") numerical plaintext in hex: 0700 ciphertext is: 2177c0b1865ac16e47807e4f4d82e421bbdf deciphered numerical plaintext in hex is: 0700 deciphered plaintext is: (shell terminal cannot display "\a\0")
PARI/GP
stigid(V,b)=subst(Pol(V),'x,b); \\ inverse function digits(...)
n = 9516311845790656153499716760847001433441357;
e = 65537;
d = 5617843187844953170308463622230283376298685;
text = "Rosetta Code"
inttext = stigid(Vecsmall(text),256) \\ message as an integer
encoded = lift(Mod(inttext, n) ^ e) \\ encrypted message
decoded = lift(Mod(encoded, n) ^ d) \\ decrypted message
message = Strchr(digits(decoded, 256)) \\ readable message
Output:
text: "Rosetta Code" inttext: 25512506514985639724585018469 encoded: 916709442744356653386978770799029131264344 decoded: 25512506514985639724585018469 message: "Rosetta Code"
If inttext is equal or greater than b = 2^(log(n)/log(2)\1) use block = inttext % b; inttext /= b; to break inttext into blocks and encode piece by piece. Decode in reverse order.
As a check: it's easy to crack this weak encrypted message without knowing secret key 'd'
f = factor(n); \\ factorize public key 'n'
crack = Strchr(digits(lift(Mod(encoded,n) ^ lift(Mod(1,(f[1,1]-1)*(f[2,1]-1)) / e)),256))
Output:
crack: "Rosetta Code"
Perl
use bigint;
$n = 9516311845790656153499716760847001433441357;
$e = 65537;
$d = 5617843187844953170308463622230283376298685;
package Message {
my @alphabet;
push @alphabet, $_ for 'A' .. 'Z', ' ';
my $rad = +@alphabet;
$code{$alphabet[$_]} = $_ for 0..$rad-1;
sub encode {
my($t) = @_;
my $cnt = my $sum = 0;
for (split '', reverse $t) {
$sum += $code{$_} * $rad**$cnt;
$cnt++;
}
$sum;
}
sub decode {
my($n) = @_;
my(@i);
while () {
push @i, $n % $rad;
last if $n < $rad;
$n = int $n / $rad;
}
reverse join '', @alphabet[@i];
}
sub expmod {
my($a, $b, $n) = @_;
my $c = 1;
do {
($c *= $a) %= $n if $b % 2;
($a *= $a) %= $n;
} while ($b = int $b/2);
$c;
}
}
my $secret_message = "ROSETTA CODE";
$numeric_message = Message::encode $secret_message;
$numeric_cipher = Message::expmod $numeric_message, $e, $n;
$text_cipher = Message::decode $numeric_cipher;
$numeric_cipher2 = Message::encode $text_cipher;
$numeric_message2 = Message::expmod $numeric_cipher2, $d, $n;
$secret_message2 = Message::decode $numeric_message2;
print <<"EOT";
Secret message is $secret_message
Secret message in integer form is $numeric_message
After exponentiation with public exponent we get: $numeric_cipher
This turns into the string $text_cipher
If we re-encode it in integer form we get $numeric_cipher2
After exponentiation with SECRET exponent we get: $numeric_message2
This turns into the string $secret_message2
EOT
- Output:
Secret message is ROSETTA CODE Secret message in integer form is 97525102075211938 After exponentiation with public exponent we get: 8326171774113983822045243488956318758396426 This turns into the string ZULYDCEZOWTFXFRRNLIMGNUPHVCJSX If we re-encode it in integer form we get 8326171774113983822045243488956318758396426 After exponentiation with SECRET exponent we get: 97525102075211938 This turns into the string ROSETTA CODE
Phix
without javascript_semantics include builtins/mpfr.e mpz n = mpz_init("9516311845790656153499716760847001433441357"), e = mpz_init("65537"), d = mpz_init("5617843187844953170308463622230283376298685"), pt = mpz_init(), ct = mpz_init() string plaintext = "Rossetta Code" -- matches C/zkl -- "Rosetta Code" -- matches D/FreeBasic/Go/Icon/J/Kotlin/Seed7. mpz_import(pt, length(plaintext), 1, 1, 0, 0, plaintext) if mpz_cmp(pt, n)>0 then ?9/0 end if mpz_powm(ct, pt, e, n); printf(1,"Encoded: %s\n", {mpz_get_str(ct)}) mpz_powm(pt, ct, d, n); printf(1,"Decoded: %s\n", {mpz_get_str(pt)}) integer size =floor((mpz_sizeinbase(pt,2)+7)/8) atom pMem = allocate(size,true) integer count = mpz_export(pMem, 1, 1, 0, 0, pt) if count>size then ?9/0 end if printf(1,"As String: %s\n", {peek({pMem,count})}) {pt, ct, n, e, d} = mpz_free({pt, ct, n, e, d})
(mpz_import() and mpz_export() are not supported under pwa/p2js)
- Output:
Encoded: 5278143020249600501803788468419399384934220 Decoded: 6531201733672758787904906421349 As String: Rossetta Code
PicoLisp
PicoLisp comes with an RSA library:
### This is a copy of "lib/rsa.l" ###
# Generate long random number
(de longRand (N)
(use (R D)
(while (=0 (setq R (abs (rand)))))
(until (> R N)
(unless (=0 (setq D (abs (rand))))
(setq R (* R D)) ) )
(% R N) ) )
# X power Y modulus N
(de **Mod (X Y N)
(let M 1
(loop
(when (bit? 1 Y)
(setq M (% (* M X) N)) )
(T (=0 (setq Y (>> 1 Y)))
M )
(setq X (% (* X X) N)) ) ) )
# Probabilistic prime check
(de prime? (N)
(and
(> N 1)
(bit? 1 N)
(let (Q (dec N) K 0)
(until (bit? 1 Q)
(setq
Q (>> 1 Q)
K (inc K) ) )
(do 50
(NIL (_prim? N Q K))
T ) ) ) )
# (Knuth Vol.2, p.379)
(de _prim? (N Q K)
(use (X J Y)
(while (> 2 (setq X (longRand N))))
(setq
J 0
Y (**Mod X Q N) )
(loop
(T
(or
(and (=0 J) (= 1 Y))
(= Y (dec N)) )
T )
(T
(or
(and (> J 0) (= 1 Y))
(<= K (inc 'J)) )
NIL )
(setq Y (% (* Y Y) N)) ) ) )
# Find a prime number with `Len' digits
(de prime (Len)
(let P (longRand (** 10 (*/ Len 2 3)))
(unless (bit? 1 P)
(inc 'P) )
(until (prime? P) # P: Prime number of size 2/3 Len
(inc 'P 2) )
# R: Random number of size 1/3 Len
(let (R (longRand (** 10 (/ Len 3))) K (+ R (% (- P R) 3)))
(when (bit? 1 K)
(inc 'K 3) )
(until (prime? (setq R (inc (* K P))))
(inc 'K 6) )
R ) ) )
# Generate RSA key
(de rsaKey (N) #> (Encrypt . Decrypt)
(let (P (prime (*/ N 5 10)) Q (prime (*/ N 6 10)))
(cons
(* P Q)
(/
(inc (* 2 (dec P) (dec Q)))
3 ) ) ) )
# Encrypt a list of characters
(de encrypt (Key Lst)
(let Siz (>> 1 (size Key))
(make
(while Lst
(let N (char (pop 'Lst))
(while (> Siz (size N))
(setq N (>> -16 N))
(inc 'N (char (pop 'Lst))) )
(link (**Mod N 3 Key)) ) ) ) ) )
# Decrypt a list of numbers
(de decrypt (Keys Lst)
(mapcan
'((N)
(let Res NIL
(setq N (**Mod N (cdr Keys) (car Keys)))
(until (=0 N)
(push 'Res (char (& `(dec (** 2 16)) N)))
(setq N (>> 16 N)) )
Res ) )
Lst ) )
### End of "lib/rsa.l" ###
# Generate 100-digit keys (private . public)
: (setq Keys (rsaKey 100))
-> (14394597526321726957429995133376978449624406217727317004742182671030....
# Encrypt
: (setq CryptText
(encrypt (car Keys)
(chop "The quick brown fox jumped over the lazy dog's back") ) )
-> (72521958974980041245760752728037044798830723189142175108602418861716...
# Decrypt
: (pack (decrypt Keys CryptText))
-> "The quick brown fox jumped over the lazy dog's back"
PowerShell
$n = [BigInt]::Parse("9516311845790656153499716760847001433441357")
$e = [BigInt]::new(65537)
$d = [BigInt]::Parse("5617843187844953170308463622230283376298685")
$plaintextstring = "Hello, Rosetta!"
$plaintext = [Text.ASCIIEncoding]::ASCII.GetBytes($plaintextstring)
[BigInt]$pt = [BigInt]::new($plaintext)
if ($n -lt $pt) {throw "`$n = $n < $pt = `$pt"}
$ct = [BigInt]::ModPow($pt, $e, $n)
"Encoded: $ct"
$dc = [BigInt]::ModPow($ct, $d, $n)
"Decoded: $dc"
$decoded = [Text.ASCIIEncoding]::ASCII.GetString($dc.ToByteArray())
"As ASCII: $decoded"
- Output:
Encoded: 8545729659809274764853392532557102329563535 Decoded: 173322416552962951144796590453843272 As ASCII: Hello, Rosetta!
Python
import binascii
n = 9516311845790656153499716760847001433441357 # p*q = modulus
e = 65537
d = 5617843187844953170308463622230283376298685
message='Rosetta Code!'
print('message ', message)
hex_data = binascii.hexlify(message.encode())
print('hex data ', hex_data)
plain_text = int(hex_data, 16)
print('plain text integer ', plain_text)
if plain_text > n:
raise Exception('plain text too large for key')
encrypted_text = pow(plain_text, e, n)
print('encrypted text integer ', encrypted_text)
decrypted_text = pow(encrypted_text, d, n)
print('decrypted text integer ', decrypted_text)
print('message ', binascii.unhexlify(hex(decrypted_text)[2:]).decode()) # [2:] slicing, to strip the 0x part
- Output:
message Rosetta Code! hex data b'526f736574746120436f646521' plain text integer 6531201667836323769493764728097 encrypted text integer 5307878626309103053766094186556322974789734 decrypted text integer 6531201667836323769493764728097 message Rosetta Code!
Racket
This implementation does key generation and demonstrates digital signature as a freebie.
Thanks again to the wonderful math/number-theory package (distributed as standard).
Cutting messages into blocks has not been done.
#lang racket
(require math/number-theory)
(define-logger rsa)
(current-logger rsa-logger)
;; -| STRING TO NUMBER MAPPING |----------------------------------------------------------------------
(define (bytes->number B) ; We'll need our data in numerical form ..
(for/fold ((rv 0)) ((b B)) (+ b (* rv 256))))
(define (number->bytes N) ; .. and back again
(define (inr n b) (if (zero? n) b (inr (quotient n 256) (bytes-append (bytes (modulo n 256)) b))))
(inr N (bytes)))
;; -| RSA PUBLIC / PRIVATE FUNCTIONS |----------------------------------------------------------------
;; The basic definitions... pretty well lifted from the text book!
(define ((C e n) p)
;; Just do the arithmetic to demonstrate RSA...
;; breaking large messages into blocks is something for another day.
(unless (< p n) (raise-argument-error 'C (format "(and/c integer? (</c ~a))" n) p))
(modular-expt p e n))
(define ((P d n) c)
(modular-expt c d n))
;; -| RSA KEY GENERATION |----------------------------------------------------------------------------
;; Key generation
;; Full description of the steps can be found on Wikipedia
(define (RSA-keyset function-base-name)
(log-info "RSA-keyset: ~s" function-base-name)
(define max-k 4294967087)
;; I'm guessing this RNG is about as cryptographically strong as replacing spaces with tabs.
(define (big-random n-rolls)
(for/fold ((rv 1)) ((roll (in-range n-rolls 0 -1))) (+ (* rv (add1 max-k)) 1 (random max-k))))
(define (big-random-prime)
(define start-number (big-random (/ 1024 32)))
(log-debug "got large (possibly non-prime) number, finding next prime")
(next-prime (match start-number ((? odd? o) o) ((app add1 e) e))))
;; [1] Choose two distinct prime numbers p and q.
(log-debug "generating p")
(define p (big-random-prime))
(log-debug "p generated")
(log-debug "generating q")
(define q (big-random-prime))
(log-debug "q generated")
(log-info "primes generated")
;; [2] Compute n = pq.
(define n (* p q))
;; [3] Compute φ(n) = φ(p)φ(q) = (p − 1)(q − 1) = n - (p + q -1),
;; where φ is Euler's totient function.
(define φ (- n (+ p q -1)))
;; [4] Choose an integer e such that 1 < e < φ(n) and gcd(e, φ(n)) = 1; i.e., e and φ(n) are
;; coprime. ... most commonly 2^16 + 1 = 65,537 ...
(define e (+ (expt 2 16) 1))
;; [5] Determine d as d ≡ e−1 (mod φ(n)); i.e., d is the multiplicative inverse of e (modulo φ(n)).
(log-debug "generating d")
(define d (modular-inverse e φ))
(log-info "d generated")
(values n e d))
;; -| GIVE A USABLE SET OF PRIVATE STUFF TO A USER |--------------------------------------------------
;; six values: the public (encrypt) function (numeric)
;; the private (decrypt) function (numeric)
;; the public (encrypt) function (bytes)
;; the private (decrypt) function (bytes)
;; private (list n e d)
;; public (list n e)
(define (RSA-key-pack #:function-base-name function-base-name)
(define (rnm-fn f s) (procedure-rename f (string->symbol (format "~a-~a" function-base-name s))))
(define-values (n e d) (RSA-keyset function-base-name))
(define my-C (rnm-fn (C e n) "C"))
(define my-P (rnm-fn (P d n) "P"))
(define my-encrypt (rnm-fn (compose number->bytes my-C bytes->number) "encrypt"))
(define my-decrypt (rnm-fn (compose number->bytes my-P bytes->number) "decrypt"))
(values my-C my-P my-encrypt my-decrypt (list n e d) (list n e)))
;; -| HEREON IS JUST A LOAD OF CHATTY DEMOS |---------------------------------------------------------
(define (narrated-encrypt-bytes C who plain-text)
(define plain-n (bytes->number plain-text))
(define cypher-n (C plain-n))
(define cypher-text (number->bytes cypher-n))
(printf #<<EOS
~a wants to send plain text: ~s
as number: ~s
cyphered number: ~s
sent by ~a over the public interwebs:
~s
...
EOS
who plain-text plain-n cypher-n who cypher-text)
cypher-text)
(define (narrated-decrypt-bytes P who cypher-text)
(define cypher-n (bytes->number cypher-text))
(define plain-n (P cypher-n))
(define plain-text (number->bytes plain-n))
(printf #<<EOS
...
~s
received by ~a
as number: ~s
decyphered (with P) number: ~s
decyphered text:
~s
EOS
cypher-text who cypher-n plain-n plain-text)
plain-text)
;; ENCRYPT AND DECRYPT A MESSAGE WITH THE e.g. KEYS
(define-values (given-n given-e given-d)
(values 9516311845790656153499716760847001433441357
65537
5617843187844953170308463622230283376298685))
;; Get the keys specific RSA functions
(for ((message-text (list #"hello world" #"TOP SECRET!")))
(define Bobs-public-function (C given-e given-n))
(define Bobs-private-function (P given-d given-n))
(define cypher-text (narrated-encrypt-bytes Bobs-public-function "Alice" message-text))
(define plain-text (narrated-decrypt-bytes Bobs-private-function "Bob" cypher-text))
plain-text)
;; Demonstrate with larger keys.
;; (And include a free recap on digital signatures, too)
(define-values (A-pub-C A-pvt-P A-pub-encrypt A-pvt-decrypt A-pvt-keys A-pub-keys)
(RSA-key-pack #:function-base-name 'Alice))
(define-values (B-pub-C B-pvt-P B-pub-encrypt B-pvt-decrypt B-pvt-keys B-pub-keys)
(RSA-key-pack #:function-base-name 'Bob))
;; Since p and q are random, it is possible that message' = "message modulo {A,B}-key-n" will be too
;; big for "message' modulo {B,A}-key-n", if that happens then I run the program again until it
;; works. Strictly, we need blocking of the signed message -- which is not yet implemented.
(let* ((plain-A-to-B #"Dear Bob, meet you in Lymm at 1200, Alice")
(signed-A-to-B (A-pvt-decrypt plain-A-to-B))
(unsigned-A-to-B (A-pub-encrypt signed-A-to-B))
(crypt-signed-A-to-B (B-pub-encrypt signed-A-to-B))
(decrypt-signed-A-to-B (B-pvt-decrypt crypt-signed-A-to-B))
(decrypt-verified-B (A-pub-encrypt decrypt-signed-A-to-B)))
(printf
#<<EOS
Alice wants to send ~s to Bob.
She "encrypts" with her private "decryption" key.
(A-prv msg) -> ~s
Only she could have done this (only she has the her private key data) -- so this is a signature on the
message. Anyone can verify the signature by "decrypting" the message with the public "encryption" key.
(A-pub (A-prv msg)) -> ~s
But anyone is able to do this, so there is no privacy here.
Everyone knows that it can only be Alice at Lymm at noon, but this message is for Bob's eyes only.
We need to encrypt this with his public key:
(B-pub (A-prv msg)) -> ~s
Which is what gets posted to alt.chat.secret-rendezvous
Bob decrypts this to get the signed message from Alice:
(B-prv (B-pub (A-prv msg))) -> ~s
And verifies Alice's signature:
(A-pub (B-prv (B-pub (A-prv msg)))) -> ~s
Alice genuinely sent the message.
And nobody else (on a.c.s-r, at least) has read it.
KEYS:
Alice's full set: ~s
Bob's full set: ~s
EOS
plain-A-to-B signed-A-to-B unsigned-A-to-B crypt-signed-A-to-B decrypt-signed-A-to-B
decrypt-verified-B A-pvt-keys B-pvt-keys))
- Output:
Alice wants to send plain text: #"hello world" as number: 126207244316550804821666916 cyphered number: 4109627268073579506944196826730512948879423 sent by Alice over the public interwebs: #"/-\e\355\225\327\244\222<R@\20\4\233\275\333`?" ... ... #"/-\e\355\225\327\244\222<R@\20\4\233\275\333`?" received by Bob as number: 4109627268073579506944196826730512948879423 decyphered (with P) number: 126207244316550804821666916 decyphered text: #"hello world" Alice wants to send plain text: #"TOP SECRET!" as number: 101924313868583037137409057 cyphered number: 5346093164296793050289700489360581430628365 sent by Alice over the public interwebs: #"=^\301{\17p\201AE\341D\357 \237IPP\r" ... ... #"=^\301{\17p\201AE\341D\357 \237IPP\r" received by Bob as number: 5346093164296793050289700489360581430628365 decyphered (with P) number: 101924313868583037137409057 decyphered text: #"TOP SECRET!" Alice wants to send #"Dear Bob, meet you in Lymm at 1200, Alice" to Bob. She "encrypts" with her private "decryption" key. (A-prv msg) -> #"B}\4<G\373-\217\350;\0214\226\233\236\333\215\226\225=\236\350\277X\241*J\356\302\250\350fO\5\375u\367\365\315\270\312\334\204U\332\224\322\357u=\262\326\274e\31\301\321\210:i\361\361g\361\16\5a\304X\306\313\350(^\374 \353\350t\2662\305\346a\300\244b\337JI\343\335\21j\202\236\242\335<rA\a\233\375\23\t\32(d`\237i\267\336\270\340L\26\f\260\346&\t\301\326\331k@\253\242\241VKw\365 \204U\270*\r,\334h=\257\230\320V\357\304\242\4B\240\356\200\204\252\35\20c\220LJ}\275x!\25\23\262\325{\246\304?\36\272\343\17\230\2449Q[y\334(m1\252N<\253?^#\236p\311\3006\f\245M*<\273H\333\225\256\317\322\363\273\335\303\243\354\a\253\342\312\302\372vTQ\247\r\210\343\264\323*E\364\2\ba\305Z79\273M\327\310F\301,\235\32\323" Only she could have done this (only she has the her private key data) -- so this is a signature on the message. Anyone can verify the signature by "decrypting" the message with the public "encryption" key. (A-pub (A-prv msg)) -> #"Dear Bob, meet you in Lymm at 1200, Alice" But anyone is able to do this, so there is no privacy here. Everyone knows that it can only be Alice at Lymm at noon, but this message is for Bob's eyes only. We need to encrypt this with his public key: (B-pub (A-prv msg)) -> #"\eXq\4/\207\250hs\244<ym\3716\210\357'0\351E\202D\360\177\361\325\24\310+s\340j1\36\0\213\353\254\314*\212a;\300\210\\\347\371z`\226\230 \230A\337d\31\262nwp\6m\312\320D@h\232d]{sN\312xAW\216'c\27V\5\270\267>@\305\312\210\262|tGU?\266\325\250\227\270X\235\6C\307\323D\301q{\266S\351,i\211,~X\341\225z4\320F\353\361I\313M\270&d\267m\207 \2736s_\272\307\275\31T\301\247\317@\16D\263X\"\340\262\204\277g\30\337\311o\205\236\34\370)\323\275\5\1\301>\226Q,\255\213\\\2\307\215c\342\323\16\226a\3U\254\214\275\274\214\325\f\226\347\325\225\354~\32z)\340re5I\321\254\34'T\n\220p\316#\1\347\6;*\347\303\351\342\221\244\eey\31\275y\271\2605y\344\261\202B\321E\335\212" Which is what gets posted to alt.chat.secret-rendezvous Bob decrypts this to get the signed message from Alice: (B-prv (B-pub (A-prv msg))) -> #"B}\4<G\373-\217\350;\0214\226\233\236\333\215\226\225=\236\350\277X\241*J\356\302\250\350fO\5\375u\367\365\315\270\312\334\204U\332\224\322\357u=\262\326\274e\31\301\321\210:i\361\361g\361\16\5a\304X\306\313\350(^\374 \353\350t\2662\305\346a\300\244b\337JI\343\335\21j\202\236\242\335<rA\a\233\375\23\t\32(d`\237i\267\336\270\340L\26\f\260\346&\t\301\326\331k@\253\242\241VKw\365 \204U\270*\r,\334h=\257\230\320V\357\304\242\4B\240\356\200\204\252\35\20c\220LJ}\275x!\25\23\262\325{\246\304?\36\272\343\17\230\2449Q[y\334(m1\252N<\253?^#\236p\311\3006\f\245M*<\273H\333\225\256\317\322\363\273\335\303\243\354\a\253\342\312\302\372vTQ\247\r\210\343\264\323*E\364\2\ba\305Z79\273M\327\310F\301,\235\32\323" And verifies Alice's signature: (A-pub (B-prv (B-pub (A-prv msg)))) -> #"Dear Bob, meet you in Lymm at 1200, Alice" Alice genuinely sent the message. And nobody else (on a.c.s-r, at least) has read it. KEYS: Alice's full set: (104685401856522903402850023081275254628934665755538824520013952439504139625115997713509448983980532229245117213463882915048453185855818576471069794363975118091990355601850994380420233190180031768156385491949949615002445375960925665247160785747787333124376845288066200576472845984390877385677186819996627676676634639097055255729270941154875343472575964213139374388405182305309760553726485659960423106167598201105611690471457085541574734821426421348095213778701793437599877207476950721505461275161623234401077010666082709757697115644957960465476529769011591060857755043525709942747005873747546230596592939772042294065813 65537 2717089103223300710869400327467677924284264864888101995949520623458451584636500177162207191689440855119183734075439291369721208922299577316283774359722319847940485449116507338466741179127763462435479373816422239271238530669843516739939583694050479174276592059981393826091830737132442474221232201364332570578846365932454353567371199951546467136016124284306002875511872761969350668537869576342139916560099770887726733315363999637008436783521647128919138309876487426046116064403375745886449924998134881929018589019826525209406457786746758225025770316010686323085528641486882271019011944746635302695471929361680924424193) Bob's full set: (66453628687555934925745945778628604864426900808865010224295559035622434292221884343034084372211796572669001844069872620681089178469116242843088008182594366670325110214571956032739850447309116856946000976960287962443982329056724158946509616005091553738944083845350969457626620995817549009173612137879065054069514627974682257866567361928526254468372096924822844681482943840826594855542477801468633973217959659919448029041762191501507078772425126221108904380853918736930072466664169841898502073182029626689571748335731893924787111612947107622008163390629359277338946499436753837554940480109336784185532913066463754681017 65537 40065645823449313467522156271281139875308606308813084959528059327930012759030216763756439504389958618427304726562596348031980052624474573194667691034359998325290386803002604616043604539794698176121997293172282195706991070204897106862588071733664686557012032668284371518061563321600604452438728297053809260134398419618573423334221995863281726034127469856978901426632431740449516515840848181614406772903883730243825332015822633960435748349249507976445585019837204822017018926054553157019477128528700400452557614873387735038266042290443427594857847964184247833486305612600841625002197933394323058877499979801727736278613)
The burden seems to be in finding (proving) the next large prime after the big random number. However, once keys are generated, things are pretty snappy.
Raku
(formerly Perl 6)
No blocking here. Algorithm doesn't really work if either red or black text begins with 'A'.
class RSA-message {
has ($.n, $.e, $.d); # the 3 elements that define an RSA key
my @alphabet = |('A' .. 'Z'), ' ';
my $rad = +@alphabet;
my %code = @alphabet Z=> 0 .. *;
subset Text of Str where /^^ @alphabet+ $$/;
method encode(Text $t) {
[+] %code{$t.flip.comb} Z× (1, $rad, $rad×$rad … *);
}
method decode(Int $n is copy) {
@alphabet[
gather loop {
take $n % $rad;
last if $n < $rad;
$n div= $rad;
}
].join.flip;
}
}
constant $n = 9516311845790656153499716760847001433441357;
constant $e = 65537;
constant $d = 5617843187844953170308463622230283376298685;
my $fmt = "%48s %s\n";
my $message = 'ROSETTA CODE';
printf $fmt, 'Secret message is', $message;
my $rsa = RSA-message.new: n => $n, e => $e, d => $d;
printf $fmt, 'Secret message in integer form is',
my $numeric-message = $rsa.encode: $message;
printf $fmt, 'After exponentiation with public exponent we get',
my $numeric-cipher = expmod $numeric-message, $e, $n;
printf $fmt, 'This turns into the string',
my $text-cipher = $rsa.decode: $numeric-cipher;
printf $fmt, 'If we re-encode it in integer form we get',
my $numeric-cipher2 = $rsa.encode: $text-cipher;
printf $fmt, 'After exponentiation with SECRET exponent we get',
my $numeric-message2 = expmod $numeric-cipher2, $d, $n;
printf $fmt, 'This turns into the string',
my $message2 = $rsa.decode: $numeric-message2;
- Output:
Secret message is ROSETTA CODE Secret message in integer form is 97525102075211938 After exponentiation with public exponent we get 8326171774113983822045243488956318758396426 This turns into the string ZULYDCEZOWTFXFRRNLIMGNUPHVCJSX If we re-encode it in integer form we get 8326171774113983822045243488956318758396426 After exponentiation with SECRET exponent we get 97525102075211938 This turns into the string ROSETTA CODE
Ruby
#!/usr/bin/ruby
require 'openssl' # for mod_exp only
require 'prime'
def rsa_encode blocks, e, n
blocks.map{|b| b.to_bn.mod_exp(e, n).to_i}
end
def rsa_decode ciphers, d, n
rsa_encode ciphers, d, n
end
# all numbers in blocks have to be < modulus, or information is lost
# for secure encryption only use big modulus and blocksizes
def text_to_blocks text, blocksize=64 # 1 hex = 4 bit => default is 256bit
text.each_byte.reduce(""){|acc,b| acc << b.to_s(16).rjust(2, "0")} # convert text to hex (preserving leading 0 chars)
.each_char.each_slice(blocksize).to_a # slice hexnumbers in pieces of blocksize
.map{|a| a.join("").to_i(16)} # convert each slice into internal number
end
def blocks_to_text blocks
blocks.map{|d| d.to_s(16)}.join("") # join all blocks into one hex-string
.each_char.each_slice(2).to_a # group into pairs
.map{|s| s.join("").to_i(16)} # number from 2 hexdigits is byte
.flatten.pack("C*") # pack bytes into ruby-string
.force_encoding(Encoding::default_external) # reset encoding
end
def generate_keys p1, p2
n = p1 * p2
t = (p1 - 1) * (p2 - 1)
e = 2.step.each do |i|
break i if i.gcd(t) == 1
end
d = 1.step.each do |i|
break i if (i * e) % t == 1
end
return e, d, n
end
p1, p2 = Prime.take(100).last(2)
public_key, private_key, modulus =
generate_keys p1, p2
print "Message: "
message = gets
blocks = text_to_blocks message, 4 # very small primes
print "Numbers: "; p blocks
encoded = rsa_encode(blocks, public_key, modulus)
print "Encrypted as: "; p encoded
decoded = rsa_decode(encoded, private_key, modulus)
print "Decrypted to: "; p decoded
final = blocks_to_text(decoded)
print "Decrypted Message: "; puts final
- Output:
% echo "☆ rosettacode.org ✓" | ./rsa.rb Message: Numbers: [58008, 34336, 29295, 29541, 29812, 24931, 28516, 25902, 28530, 26400, 58012, 37642] Encrypted as: [8509, 99626, 21784, 139807, 81066, 67678, 183438, 147659, 261822, 85962, 150227, 167121] Decrypted to: [58008, 34336, 29295, 29541, 29812, 24931, 28516, 25902, 28530, 26400, 58012, 37642] Decrypted Message: ☆ rosettacode.org ✓
Rust
extern crate num;
use num::bigint::BigUint;
use num::integer::Integer;
use num::traits::{One, Zero};
fn mod_exp(b: &BigUint, e: &BigUint, n: &BigUint) -> Result<BigUint, &'static str> {
if n.is_zero() {
return Err("modulus is zero");
}
if b >= n {
// base is too large and should be split into blocks
return Err("base is >= modulus");
}
if b.gcd(n) != BigUint::one() {
return Err("base and modulus are not relatively prime");
}
let mut bb = b.clone();
let mut ee = e.clone();
let mut result = BigUint::one();
while !ee.is_zero() {
if ee.is_odd() {
result = (result * &bb) % n;
}
ee >>= 1;
bb = (&bb * &bb) % n;
}
Ok(result)
}
fn main() {
let msg = "Rosetta Code";
let n = "9516311845790656153499716760847001433441357"
.parse()
.unwrap();
let e = "65537".parse().unwrap();
let d = "5617843187844953170308463622230283376298685"
.parse()
.unwrap();
let msg_int = BigUint::from_bytes_be(msg.as_bytes());
let enc = mod_exp(&msg_int, &e, &n).unwrap();
let dec = mod_exp(&enc, &d, &n).unwrap();
let msg_dec = String::from_utf8(dec.to_bytes_be()).unwrap();
println!("msg as txt: {}", msg);
println!("msg as num: {}", msg_int);
println!("enc as num: {}", enc);
println!("dec as num: {}", dec);
println!("dec as txt: {}", msg_dec);
}
- Output:
msg as txt: Rosetta Code msg as num: 25512506514985639724585018469 enc as num: 916709442744356653386978770799029131264344 dec as num: 25512506514985639724585018469 dec as txt: Rosetta Code
Scala
The code below demonstrates RSA encryption and decryption in Scala. Text to integer encryption using ASCII code.
object RSA_saket{
val d = BigInt("5617843187844953170308463622230283376298685")
val n = BigInt("9516311845790656153499716760847001433441357")
val e = 65537
val text = "Rosetta Code"
val encode = (msg:BigInt) => pow_mod(msg,e,n)
val decode = (msg:BigInt) => pow_mod(msg,d,n)
val getmsg = (txt:String) => BigInt(txt.map(x => "%03d".format(x.toInt)).reduceLeft(_+_))
def pow_mod(p:BigInt, q:BigInt, n:BigInt):BigInt = {
if(q==0) BigInt(1)
else if(q==1) p
else if(q%2 == 1) pow_mod(p,q-1,n)*p % n
else pow_mod(p*p % n,q/2,n)
}
def gettxt(num:String) = {
if(num.size%3==2)
("0" + num).grouped(3).toList.foldLeft("")(_ + _.toInt.toChar)
else
num.grouped(3).toList.foldLeft("")(_ + _.toInt.toChar)
}
def main(args: Array[String]): Unit = {
println(f"Original String \t: "+text)
val msg = getmsg(text)
println(f"Converted Signal \t: "+msg)
val enc_sig = encode(msg)
println("Encoded Signal \t\t: "+ enc_sig)
val dec_sig = decode(enc_sig)
println("Decoded String \t\t: "+ dec_sig)
val rec_msg = gettxt(dec_sig.toString)
println("Retrieved Signal \t: "+rec_msg)
}
}
- Output:
Ouput: Original String : Rosetta Code Converted String : 82111115101116116097032067111100101 Encoded Signal : 5902559240035849005218240192859088445397686 Decoded String : 82111115101116116097032067111100101 Retrieved String : Rosetta Code
Seed7
$ include "seed7_05.s7i";
include "bigint.s7i";
include "bytedata.s7i";
const proc: main is func
local
const string: plainText is "Rosetta Code";
# Use a key big enough to hold 16 bytes of plain text in a single block.
const bigInteger: modulus is 9516311845790656153499716760847001433441357_;
const bigInteger: encode is 65537_;
const bigInteger: decode is 5617843187844953170308463622230283376298685_;
var bigInteger: plainTextNumber is 0_;
var bigInteger: encodedNumber is 0_;
var bigInteger: decodedNumber is 0_;
var string: decodedText is "";
begin
writeln("Plain text: " <& plainText);
plainTextNumber := bytes2BigInt(plainText, UNSIGNED, BE);
if plainTextNumber >= modulus then
writeln("Plain text message too long");
else
writeln("Plain text as a number: " <& plainTextNumber);
encodedNumber := modPow(plainTextNumber, encode, modulus);
writeln("Encoded: " <& encodedNumber);
decodedNumber := modPow(encodedNumber, decode, modulus);
writeln("Decoded: " <& decodedNumber);
decodedText := bytes(decodedNumber, UNSIGNED, BE);
writeln("Decoded number as text: " <& decodedText);
end if;
end func;
- Output:
Plain text: Rosetta Code Plain text as a number: 25512506514985639724585018469 Encoded: 916709442744356653386978770799029131264344 Decoded: 25512506514985639724585018469 Decoded number as text: Rosetta Code
Sidef
const n = 9516311845790656153499716760847001433441357
const e = 65537
const d = 5617843187844953170308463622230283376298685
module Message {
var alphabet = [('A' .. 'Z')..., ' ']
var rad = alphabet.len
var code = Hash(^rad -> map {|i| (alphabet[i], i) }...)
func encode(String t) {
[code{t.reverse.chars...}] ~Z* t.len.range.map { |i| rad**i } -> sum(0)
}
func decode(Number n) {
''.join(alphabet[
gather {
loop {
var (d, m) = n.divmod(rad)
take(m)
break if (n < rad)
n = d
}
}...]
).reverse
}
}
var secret_message = "ROSETTA CODE"
say "Secret message is #{secret_message}"
var numeric_message = Message::encode(secret_message)
say "Secret message in integer form is #{numeric_message}"
var numeric_cipher = expmod(numeric_message, e, n)
say "After exponentiation with public exponent we get: #{numeric_cipher}"
var text_cipher = Message::decode(numeric_cipher)
say "This turns into the string #{text_cipher}"
var numeric_cipher2 = Message::encode(text_cipher)
say "If we re-encode it in integer form we get #{numeric_cipher2}"
var numeric_message2 = expmod(numeric_cipher2, d, n)
say "After exponentiation with SECRET exponent we get: #{numeric_message2}"
var secret_message2 = Message::decode(numeric_message2)
say "This turns into the string #{secret_message2}"
- Output:
Secret message is ROSETTA CODE Secret message in integer form is 97525102075211938 After exponentiation with public exponent we get: 8326171774113983822045243488956318758396426 This turns into the string ZULYDCEZOWTFXFRRNLIMGNUPHVCJSX If we re-encode it in integer form we get 8326171774113983822045243488956318758396426 After exponentiation with SECRET exponent we get: 97525102075211938 This turns into the string ROSETTA CODE
Tcl
This code is careful to avoid the assumption that the input string is in a single-byte encoding, instead forcing the encryption to be performed on the UTF-8 form of the text.
package require Tcl 8.5
# This is a straight-forward square-and-multiply implementation that relies on
# Tcl 8.5's bignum support (based on LibTomMath) for speed.
proc modexp {b expAndMod} {
lassign $expAndMod -> e n
if {$b >= $n} {puts stderr "WARNING: modulus too small"}
for {set r 1} {$e != 0} {set e [expr {$e >> 1}]} {
if {$e & 1} {
set r [expr {($r * $b) % $n}]
}
set b [expr {($b ** 2) % $n}]
}
return $r
}
# Assumes that messages are shorter than the modulus
proc rsa_encrypt {message publicKey} {
if {[lindex $publicKey 0] ne "publicKey"} {error "key handling"}
set toEnc 0
foreach char [split [encoding convertto utf-8 $message] ""] {
set toEnc [expr {$toEnc * 256 + [scan $char "%c"]}]
}
return [modexp $toEnc $publicKey]
}
proc rsa_decrypt {encrypted privateKey} {
if {[lindex $privateKey 0] ne "privateKey"} {error "key handling"}
set toDec [modexp $encrypted $privateKey]
for {set message ""} {$toDec > 0} {set toDec [expr {$toDec >> 8}]} {
append message [format "%c" [expr {$toDec & 255}]]
}
return [encoding convertfrom utf-8 [string reverse $message]]
}
# Assemble packaged public and private keys
set e 65537
set n 9516311845790656153499716760847001433441357
set d 5617843187844953170308463622230283376298685
set publicKey [list "publicKey" $e $n]
set privateKey [list "privateKey" $d $n]
# Test on some input strings
foreach input {"Rosetta Code" "UTF-8 \u263a test"} {
set enc [rsa_encrypt $input $publicKey]
set dec [rsa_decrypt $enc $privateKey]
puts "$input -> $enc -> $dec"
}
Output:
Rosetta Code -> 916709442744356653386978770799029131264344 -> Rosetta Code UTF-8 ☺ test -> 3905697186829810541171404594906488782823186 -> UTF-8 ☺ test
Visual Basic .NET
Imports System
Imports System.Numerics
Imports System.Text
Module Module1
Sub Main()
Dim n As BigInteger = BigInteger.Parse("9516311845790656153499716760847001433441357")
Dim e As BigInteger = 65537
Dim d As BigInteger = BigInteger.Parse("5617843187844953170308463622230283376298685")
Dim plainTextStr As String = "Hello, Rosetta!"
Dim plainTextBA As Byte() = ASCIIEncoding.ASCII.GetBytes(plainTextStr)
Dim pt As BigInteger = New BigInteger(plainTextBA)
If pt > n Then Throw New Exception() ' Blocking not implemented
Dim ct As BigInteger = BigInteger.ModPow(pt, e, n)
Console.WriteLine(" Encoded: " & ct.ToString("X"))
Dim dc As BigInteger = BigInteger.ModPow(ct, d, n)
Console.WriteLine(" Decoded: " & dc.ToString("X"))
Dim decoded As String = ASCIIEncoding.ASCII.GetString(dc.ToByteArray())
Console.WriteLine("As ASCII: " & decoded)
End Sub
End Module
- Output:
Encoded: 6219A470D8B319A31C8E13F612B31337098F Decoded: 2161747465736F52202C6F6C6C6548 As ASCII: Hello, Rosetta!
V (Vlang)
/*import math.big
fn main() {
//var bb, ptn, etn, dtn big.Int
pt := "Rosetta Code"
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 := big.integer_from_string("9516311845790656153499716760847001433441357")?
e := big.integer_from_string("65537")?
d := big.integer_from_string("5617843187844953170308463622230283376298685")?
mut ptn := big.zero_int
// convert plain text to a number
for b in pt.bytes() {
bb := big.integer_from_i64(i64(b))
ptn = ptn.lshift(8).bitwise_or(bb)
}
if ptn >= n {
println("Plain text message too long")
return
}
println("Plain text as a number:$ptn")
// encode a single number
etn := ptn.big_mod_pow(e,n)
println("Encoded: $etn")
// decode a single number
mut dtn := etn.big_mod_pow(d,n)
println("Decoded: $dtn")
// convert number to text
mut db := [16]u8{}
mut dx := 16
bff := big.integer_from_int(0xff)
for dtn.bit_len() > 0 {
dx--
bb := dtn.bitwise_and(bff)
db[dx] = u8(i64(bb.int()))
dtn = dtn.rshift(8)
println('${db[0..].bytestr()} ${dtn.bit_len()}')
}
println("Decoded number as text: ${db[dx..].bytestr()}")
}*/
import math.big
fn main() {
//var bb, ptn, etn, dtn big.Int
pt := "Hello World"
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 := big.integer_from_string("9516311845790656153499716760847001433441357")?
e := big.integer_from_string("65537")?
d := big.integer_from_string("5617843187844953170308463622230283376298685")?
mut ptn := big.zero_int
// convert plain text to a number
for b in pt.bytes() {
bb := big.integer_from_i64(i64(b))
ptn = ptn.lshift(8).bitwise_or(bb)
}
if ptn >= n {
println("Plain text message too long")
return
}
println("Plain text as a number:$ptn")
// encode a single number
etn := ptn.big_mod_pow(e,n)
println("Encoded: $etn")
// decode a single number
mut dtn := etn.big_mod_pow(d,n)
println("Decoded: $dtn")
// convert number to text
mut db := [16]u8{}
mut dx := 16
bff := big.integer_from_int(0xff)
for dtn.bit_len() > 0 {
dx--
bb := dtn.bitwise_and(bff)
db[dx] = u8(i64(bb.int()))
dtn = dtn.rshift(8)
}
println("Decoded number as text: ${db[dx..].bytestr()}")
}
- Output:
Plain text: Hello World Plain text as a number:87521618088882533792115812 Encoded: 8455179966388263657372423602482472996174613 Decoded: 87521618088882533792115812 Decoded number as text: Hello World
Wren
import "./big" for BigInt
var pt = "Rosetta Code"
System.print("Plain text: : %(pt)")
var n = BigInt.new("9516311845790656153499716760847001433441357")
var e = BigInt.new("65537")
var d = BigInt.new("5617843187844953170308463622230283376298685")
var ptn = BigInt.zero
// convert plain text to a number
for (b in pt.bytes) {
ptn = (ptn << 8) | BigInt.new(b)
}
if (ptn >= n) {
System.print("Plain text message too long")
return
}
System.print("Plain text as a number : %(ptn)")
// encode a single number
var etn = ptn.modPow(e, n)
System.print("Encoded : %(etn)")
// decode a single number
var dtn = etn.modPow(d, n)
System.print("Decoded : %(dtn)")
// convert number to text
var db = List.filled(16, 0)
var dx = 16
var bff = BigInt.new(255)
while (dtn.bitLength > 0) {
dx = dx - 1
db[dx] = (dtn & bff).toSmall
dtn = dtn >> 8
}
var s = ""
for (i in dx..15) s = s + String.fromByte(db[i])
System.print("Decoded number as text : %(s)")
- Output:
Plain text: : Rosetta Code Plain text as a number : 25512506514985639724585018469 Encoded : 916709442744356653386978770799029131264344 Decoded : 25512506514985639724585018469 Decoded number as text : Rosetta Code
zkl
No blocking.
var BN=Import.lib("zklBigNum");
n:=BN("9516311845790656153499716760847001433441357");
e:=BN("65537");
d:=BN("5617843187844953170308463622230283376298685");
const plaintext="Rossetta Code";
pt:=BN(Data(Int,0,plaintext)); // convert string (as stream of bytes) to big int
if(pt>n) throw(Exception.ValueError("Message is too large"));
println("Plain text: ",plaintext);
println("As Int: ",pt);
ct:=pt.powm(e,n); println("Encoded: ",ct);
pt =ct.powm(d,n); println("Decoded: ",pt);
txt:=pt.toData().text; // convert big int to bytes, treat as string
println("As String: ",txt);
- Output:
Plain text: Rossetta Code As Int: 6531201733672758787904906421349 Encoded: 5278143020249600501803788468419399384934220 Decoded: 6531201733672758787904906421349 As String: Rossetta Code
- Programming Tasks
- Encryption
- 11l
- Ada
- ALGOL 68
- C
- GMP
- C sharp
- System.Numerics
- Common Lisp
- D
- Delphi
- System.SysUtils
- Velthuis.BigIntegers
- Erlang
- F Sharp
- FreeBASIC
- Go
- Haskell
- Icon
- Unicon
- J
- Java
- Jq
- Julia
- Kotlin
- Mathematica
- Wolfram Language
- Nim
- PARI/GP
- Perl
- Phix
- Phix/mpfr
- PicoLisp
- PowerShell
- Python
- Racket
- Raku
- Ruby
- Rust
- Scala
- Seed7
- Sidef
- Tcl
- Visual Basic .NET
- V (Vlang)
- Wren
- Wren-big
- Zkl