################################
# SCRIPT: rsa_make_exact.bdscr #
################################
# make an RSA key pair of exact bit length
e=0x10001 # Set public exponent, e
printf("e=%x\n",e);
k=511 # required modulus size
println("Required modulus size=", k)
h=k/2 # create a prime of length half k with *two* highest bits set
repeat p=genprime(h); printf("try p=%x\n", p); until ((p mod e ne 1) and (getbit(p,h-2) eq 1)); 
printf("p=%x\n",p)
println("gcd(p-1,e)=",gcd(p-1,e)) # Check gcd's
h=k-k/2   # and another prime of length to make the full size
repeat q=genprime(h); printf("try q=%x\n", q); until ((q mod e ne 1) and (getbit(q,h-2) eq 1)); 
printf("q=%x\n", q)
println("gcd(q-1,e)=",gcd(q-1,e)) # Check gcd's
n=p*q # Compute modulus N
printf("N=%x\n",n)
println("bitlen(N)=",bitlen(n))
##assert(bitlen(N) == k)
L=(p-1)*(q-1) # Compute Euler phi
d=modinv(e,L) # Compute private exponent, d
printf("d=%x\n",d)
# Create a random test message
m=randbits(k-2) # Make sure m is shorter than N
println("A random test message of length ", bitlen(m), " bits < ", bitlen(n))
printf("m=%x\n", m)
c=modexp(m,e,n) # Compute encrypted message
puts "Encrypted form..."
printf("c=%x\n",c)
puts "Check decryption y of c gives same m..."
y=modexp(c,d,n)
printf("y=%x\n",y)
printf("y == m is %q\n", y == m)
puts "Now sign the message using the private key..."
s=modexp(m, d, n)
printf("s=%x\n", s)
puts "and verify with the public key..."
v= modexp(s, e, n)
printf("v=%x\n", v)
printf("v == m is %q\n", v == m)