extra/crypto/rsa/rsa.factor

   1 ! Copyright (C) 2008 Doug Coleman.
   2 ! See http://factorcode.org/license.txt for BSD license.
   3 USING: math.primes kernel math math.functions namespaces
   4 sequences accessors ;
   5 IN: crypto.rsa
   6
   7 ! The private key is the only secret.
   8
   9 ! p,q are two random primes of numbits/2
  10 ! phi = (p-1)(q-1)
  11 ! modulus = p*q
  12 ! public = 65537
  13 ! private = public modinv phi
  14
  15 TUPLE: rsa modulus private-key public-key ;
  16
  17 C: <rsa> rsa
  18
  19 <PRIVATE
  20
  21 CONSTANT: public-key 65537
  22
  23 : rsa-primes ( numbits -- p q )
  24     2/ 2 swap unique-primes first2 ;
  25
  26 : modulus-phi ( numbits -- n phi )
  27     #! Loop until phi is not divisible by the public key.
  28     dup rsa-primes [ * ] 2keep
  29     [ 1 - ] bi@ *
  30     dup public-key gcd nip 1 = [
  31         rot drop
  32     ] [
  33         2drop modulus-phi
  34     ] if ;
  35
  36 PRIVATE>
  37
  38 : generate-rsa-keypair ( numbits -- <rsa> )
  39     modulus-phi
  40     public-key over mod-inv +
  41     public-key <rsa> ;
  42
  43 : rsa-encrypt ( message rsa -- encrypted )
  44     [ public-key>> ] [ modulus>> ] bi ^mod ;
  45
  46 : rsa-decrypt ( encrypted rsa -- message )
  47     [ private-key>> ] [ modulus>> ] bi ^mod ;