RSA DEMO
Function for RSA in VBA
***copy & paste to the Module
Function randPrime(nBit As Long)
Dim nr As Long
nr = Int(((2 ^ nBit - 1) - (2 ^ (nBit - 1)) + 1) * Rnd + (2 ^ (nBit - 1)))
While IsPrime(nr) = False
nr = Int(((2 ^ nBit - 1) - (2 ^ (nBit - 1)) + 1) * Rnd + (2 ^ (nBit - 1)))
Wend
randPrime = nr
End Function
Function IsPrime(Num As Long) As Boolean
'http://eforexcel.com/wp/vba-a-function-to-check-whether-a-given-number-is-prime/
Dim i As Long
If Int(Num / 2) = (Num / 2) Then
Exit Function
Else
For i = 3 To Sqr(Num) Step 2
If Int(Num / i) = (Num / i) Then
Exit Function
End If
Next i
End If
IsPrime = True
End Function
Function modular_pow_MEM(base As LongLong, exponent As LongLong, modulus As LongLong)
'https://en.wikipedia.org/wiki/Modular_exponentiation#Memory-efficient_method
Dim c As LongLong
c = 1
Dim e_prime As LongLong
For e_prime = 0 To exponent - 1
c = (c * base) Mod modulus
Next e_prime
modular_pow_MEM = c
End Function
Function modular_pow_RightToLeftBinaryMethod(b As LongLong, e As LongLong, m As LongLong)
'https://en.wikipedia.org/wiki/Modular_exponentiation#Implementation_in_Lua
Dim r As LongLong
r = 1
b = b Mod m
While e > 0
If e Mod 2 = 1 Then
r = (r * b) Mod m
End If
e = Application.WorksheetFunction.Bitrshift(e, 1)
b = (b ^ 2) Mod m
Wend
modular_pow_RightToLeftBinaryMethod = r
End Function
Function testRC(n As Long)
If n <= 0 Then
testRC = 1
Else
testRC = n * testRC(n - 1)
End If
End Function
Function modularMultiplicativeInverse(a As LongLong, n As LongLong)
'https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
Dim t As LongLong, newt As LongLong, r As LongLong, newr As LongLong, Quotient As LongLong, d As LongLong
t = 0
newt = 1
r = n
newr = a
While newr <> 0
Quotient = Int(r / newr)
'(t, newt) = (newt, t - quotient * newt)
d = newt
newt = t - Quotient * d
t = d
'(r, newr) = (newr, r - quotient * newr)
d = newr
newr = r - Quotient * d
r = d
Wend
If r > 1 Then
'return none
End If
If t < 0 Then
t = t + n
End If
modularMultiplicativeInverse = t
End Function
Function bitLength(n As Long)
bitLength = Int(Application.WorksheetFunction.Log(n, 2)) + 1
End Function
RSA in Java
import java.math.BigInteger;
import java.util.Random;
class RSADemo {
public static void main(String[] args) {
int nBit = 2024;
BigInteger p = BigInteger.probablePrime(nBit, new Random());
BigInteger q = BigInteger.probablePrime(nBit, new Random());
BigInteger n = p.multiply(q);
BigInteger z = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
BigInteger e = BigInteger.probablePrime(10, new Random());//public key : e,n
while ( !(e.gcd(z).equals(BigInteger.ONE)) ){
e = BigInteger.probablePrime(10, new Random());
}
BigInteger d = e.modInverse(z);//private key : d,n
BigInteger planT = new BigInteger("12123121212323123123");
BigInteger cipherT = planT.modPow(e, n);//enc
BigInteger planTCV = cipherT.modPow(d, n);//dec
System.out.println("public key : "+e+","+n+": bit of n = "+n.bitLength());
System.out.println(planT+"\n"+cipherT+"\n"+planTCV);
}
}
/*
* https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/math/BigInteger.html
* https://en.wikipedia.org/wiki/RSA_(cryptosystem)
*/