RSA 64-bit
Algorithm creator(s)
Ronald Rivest, Adi Shamir, Leonard Adleman
PB author(s)
Wayne Diamond
Description
The worlds first (publically disclosed) secure public key exchange system.
Note
The honour of finding an asymmetric cipher fell to James Ellis and Clifford Cocks of the British GCHQ in 1973. Sadly, due to the secrecy of their work they had to remain silent and watch while their discoveries were rediscovered 4 years later by Diffie, Hellman, Merkle, Rivest, Shamir and Adleman over the next three years. For stronger RSA we need a good PB big number library! *hint*
Source
https://forum.powerbasic.com/forum/user-to-user-discussions/source-code/23952-64-bit-rsa-public-key-cryptography-comes-to-pb?t=23327
See also
n/a
Source Code
Download source code file rsa64.bas (Right-click -> "Save as ...")
#COMPILE EXE
#INCLUDE "win32api.inc"
GLOBAL key() AS DOUBLE
GLOBAL p AS DOUBLE, q AS DOUBLE
GLOBAL PHI AS DOUBLE
DECLARE FUNCTION dec(tIp AS STRING, dD AS DOUBLE, dN AS DOUBLE) AS STRING
DECLARE FUNCTION enc(tIp AS STRING, eE AS DOUBLE, eN AS DOUBLE) AS STRING
DECLARE FUNCTION nMod(x AS DOUBLE, y AS DOUBLE) AS DOUBLE
DECLARE FUNCTION Mult(BYVAL x AS DOUBLE, BYVAL p AS DOUBLE, BYVAL m AS DOUBLE) AS DOUBLE
DECLARE FUNCTION IsPrime(lngNumber AS DOUBLE) AS BYTE
DECLARE FUNCTION GCD(nPHI AS DOUBLE) AS DOUBLE
DECLARE FUNCTION Euler(E3 AS DOUBLE, PHI3 AS DOUBLE) AS DOUBLE
DECLARE SUB keyGen()
SUB keyGen()
'Generates the keys for E, D and N
DIM E#, D#, N#
%PQ_UP = 9999 'set upper limit of random number
%PQ_LW = 3170 'set lower limit of random number
%KEY_LOWER_LIMIT = 10000000 'set for 64bit minimum
p = 0: q = 0
RANDOMIZE TIMER
DO UNTIL D > %KEY_LOWER_LIMIT 'makes sure keys are 64bit minimum
DO UNTIL IsPrime(p) AND IsPrime(q) ' make sure q and q are primes
p = INT((%PQ_UP - %PQ_LW + 1) * RND + %PQ_LW)
q = INT((%PQ_UP - %PQ_LW + 1) * RND + %PQ_LW)
LOOP
N = p * q
PHI = (p - 1) * (q - 1)
E = GCD(PHI)
D = Euler(E, PHI)
LOOP
key(1) = E
key(2) = D
key(3) = N
END SUB
FUNCTION Euler(E3 AS DOUBLE, PHI3 AS DOUBLE) AS DOUBLE
'genetates D from (E and PHI) using the Euler algorithm
ON ERROR RESUME NEXT
DIM u1#, u2#, u3#, v1#, v2#, v3#, q#
DIM t1#, t2#, t3#, z#, uu#, vv#, inverse#
u1 = 1
u2 = 0
u3 = PHI3
v1 = 0
v2 = 1
v3 = E3
DO UNTIL (v3 = 0)
q = INT(u3 / v3)
t1 = u1 - q * v1
t2 = u2 - q * v2
t3 = u3 - q * v3
u1 = v1
u2 = v2
u3 = v3
v1 = t1
v2 = t2
v3 = t3
z = 1
LOOP
uu = u1
vv = u2
IF (vv < 0) THEN
inverse = vv + PHI3
ELSE
inverse = vv
END IF
Euler = inverse
END FUNCTION
FUNCTION GCD(nPHI AS DOUBLE) AS DOUBLE
'generates a random number relatively prime to PHI
ON ERROR RESUME NEXT
DIM nE#, y#
DIM x AS DOUBLE
%N_UP = 99999999 'set upper limit of random number for E
%N_LW = 10000000 'set lower limit of random number for E
RANDOMIZE
nE = INT((%N_UP - %N_LW + 1) * RND + %N_LW)
top:
x = nPHI MOD nE
y = x MOD nE
IF y <> 0 AND IsPrime(nE) THEN
GCD = nE
EXIT FUNCTION
ELSE
nE = nE + 1
END IF
GOTO top
END FUNCTION
FUNCTION IsPrime(lngNumber AS DOUBLE) AS BYTE
'Returns '%TRUE' if lngNumber is a prime
ON ERROR RESUME NEXT
DIM lngCount#
DIM lngSqr#
DIM x#
lngSqr = INT(SQR(lngNumber)) ' Get the int square root
IF lngNumber < 2 THEN
IsPrime = %FALSE
EXIT FUNCTION
END IF
lngCount = 2
IsPrime = %TRUE
IF lngNumber MOD lngCount = 0 THEN
IsPrime = %FALSE
EXIT FUNCTION
END IF
lngCount = 3
FOR x = lngCount TO lngSqr STEP 2
IF lngNumber MOD x = 0 THEN
IsPrime = %FALSE
EXIT FUNCTION
END IF
NEXT
END FUNCTION
FUNCTION Mult(BYVAL x AS DOUBLE, BYVAL p AS DOUBLE, BYVAL m AS DOUBLE) AS DOUBLE
DIM y AS DOUBLE
'encrypts, decrypts values passed to the function.. e.g.
'Mult = M^E mod N (encrypt) where M = x , E = p, N = m
'Mult = M^D mod N (decrypt)
ON ERROR GOTO error1
y = 1
DO WHILE p > 0
DO WHILE (p / 2) = INT((p / 2))
x = nMod((x * x), m)
p = p / 2
LOOP
y = nMod((x * y), m)
p = p - 1
LOOP
Mult = y
EXIT FUNCTION
error1:
y = 0
END FUNCTION
FUNCTION nMod(x AS DOUBLE, y AS DOUBLE) AS DOUBLE
'this function replaces the Mod command. instead of z = x Mod y
'it is now z = nMod(x,y)
ON ERROR RESUME NEXT
DIM z#
z = x - (INT(x / y) * y)
nMod = z
END FUNCTION
FUNCTION GoHex(xLng AS LONG) AS STRING
ON ERROR RESUME NEXT
DIM I AS LONG
DIM xStr AS STRING
DIM OutStr$
xStr = RIGHT$("00000000" & TRIM$(STR$(xLng)), 8)
FOR I = 1 TO LEN(xStr)
OutStr$ = OutStr$ & CHR$(VAL("&h" & MID$(xStr, I, 2)))
! inc I
NEXT I
FUNCTION = OutStr$
END FUNCTION
FUNCTION enc(tIp AS STRING, eE AS DOUBLE, eN AS DOUBLE) AS STRING
ON ERROR RESUME NEXT
DIM encSt AS STRING
DIM e2st AS STRING
DIM I AS LONG
encSt = ""
e2st = ""
IF tIp = "" THEN EXIT FUNCTION
FOR i = 1 TO LEN(tIp)
encSt = encSt & GoHex(Mult(CLNG(ASC(MID$(tIp, i, 1))), eE, eN))
NEXT i
enc = encSt
END FUNCTION
FUNCTION dec(tIp AS STRING, dD AS DOUBLE, dN AS DOUBLE) AS STRING
ON ERROR RESUME NEXT
DIM decSt AS STRING
DIM z AS LONG
DIM zptr AS LONG
DIM sTmp AS STRING
DIM tok AS LONG
decSt = ""
FOR z = 1 TO LEN(tIp)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z,1)),2)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z+1,1)),2)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z+2,1)),2)
sTmp = sTmp & HEX$(ASC(MID$(tIp,z+3,1)),2)
tok = VAL(sTmp)
decSt = decSt + CHR$(Mult(tok, dD, dN))
! add z, 3
sTmp = ""
NEXT z
dec = decSt
END FUNCTION
'/////////////////////////////////////////////////////
'// Demo program - creates private and public keys, //
'// then encrypts and decrypts a test string. //
'/////////////////////////////////////////////////////
FUNCTION PBMAIN() AS LONG
REDIM key(3) AS DOUBLE
DIM EncStr AS STRING
DIM DecStr AS STRING
DIM PlainText AS STRING
PlainText = "ABCDEFGHIJKLMNOPQRSTUVWXYZ 1234567890" 'The message to encrypt
keyGen
STDOUT "Result:"
STDOUT " p=" & STR$(p)
STDOUT " q=" & STR$(q)
STDOUT " PHI=" & STR$(PHI)
STDOUT " E=" & LEFT$(STR$(Key(1)) & SPACE$(12),12) & "PRIVATE KEY"
STDOUT " D=" & LEFT$(STR$(Key(2)) & SPACE$(12),12) & "PUBLIC KEY"
STDOUT " N=" & LEFT$(STR$(Key(3)) & SPACE$(12),12) & "PUBLIC KEY"
STDOUT
STDOUT "Plaintext: " & PlainText
EncStr = enc(Plaintext, key(1), key(3))
STDOUT "Encrypted: " & EncStr
DecStr = dec(EncStr, key(2), key(3))
STDOUT "Decrypted: " & DecStr
WAITKEY$
END FUNCTION