-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathrsa.zp
178 lines (155 loc) · 6.47 KB
/
rsa.zp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
;; rsa.scm -- RSA public key cryptography library
;; Copyright (c) 2014 Alex Shinn. All rights reserved.
;; BSD-style license: http://synthcode.com/license.txt
;; Modified for use with zepto by Veit Heller
;; The RSA key type. The public fields are always present, but the
;; private key d may be #f.
(define-record-type rsa-key
(rsa:make-rsa-key bits n e d)
rsa:rsa-key?
(bits rsa:key-bits)
(n rsa:key-n)
(e rsa:key-e)
(d rsa:key-d))
(module "rsa"
(export
(list "key-gen-from-primes" key-gen-from-primes)
(list "key-gen" key-gen)
(list "pub-key" pub-key)
(list "encrypt" encrypt)
(list "decrypt" decrypt)
(list "sign" sign)
(list "verify" verify)
(list "verify?" verify?))
(key-gen-from-primes (lambda (bit-length p q . o)
"Given a bit-length and two primes, generates a rsa key.
params:
- bit-length: the key bit length
- p: the first prime
- q: the second prime (must be coprime)
complexity: O(1)
returns: a RSA key"
(define (choose-exponent phi e)
(cond ((>= e phi) (error "couldn't find an exponent for " p q))
((= 1 (math:gcd e phi)) e)
(else (choose-exponent phi (+ e 2)))))
(let* ((n (* p q))
(phi (* (- p 1) (- q 1)))
(e (choose-exponent phi (cond ((pair? o) (car o))
((< 65537 phi) 65537)
(else 3))))
(d (math:modular-inverse e phi)))
(rsa:make-rsa-key bit-length n e d))))
(key-gen (lambda o
"generates a RSA key. Defaults to 1024 bits length if not given an argument.
Frontend for <fun>rsa:key-gen-from-primes</fun> that generates prime numbers.
params:
- o: the size of the key to generate (optional)
complexity: random (because of the prime generation
returns: a new key"
(let* ((bit-length (if (null? o) 1024 (car o)))
(lo (max 3 (expt 2 (- bit-length 1))))
(hi (expt 2 bit-length))
(_ (random (crypto:randint)))
(p (random-prime lo hi))
(q (random-prime-distinct-from lo hi p)))
(key-gen-from-primes bit-length p q))))
(pub-key (lambda (priv-key)
"Returns a copy of the given key with the private key, if any, removed."
(rsa:make-rsa-key (rsa:key-bits priv-key) (rsa:key-n priv-key)
(rsa:key-e priv-key) #f)))
(pkcs1-pad (lambda (bv)
"From RFC-1423"
(let ((pad (- 8 (modulo (byte-vector:length bv) 8))))
(++ bv (make-byte-vector pad pad)))))
(pkcs1-unpad (lambda (bv)
(let* ((len (byte-vector:length bv))
(pad (byte-vector:ref bv (- len 1))))
(if (not (and (<= 1 pad) (<= pad 8)))
(error "not pkcs1 padded" bv)
(byte-vector:subvector bv 0 (- len pad))))))
(encrypt-integer (lambda (pub-key msg)
"Actual encryption and decryption are trivially defined as modular exponentiation."
(if (>= msg (rsa:key-n pub-key))
(error "message larger than modulus" msg (rsa:key-n pub-key)))
(math:modpow msg (rsa:key-e pub-key) (rsa:key-n pub-key))))
(decrypt-integer (lambda (priv-key cipher)
(if (>= cipher (rsa:key-n priv-key))
(error "cipher larger than modulus"))
(math:modpow cipher (rsa:key-d priv-key) (rsa:key-n priv-key))))
(convert-plain (lambda (f key msg)
"Arbitrary messages are encrypted by converting encoded bytevectors
to and from integers.
TODO: user emsa-pss encoding"
(cond
((byte-vector? msg)
(integer->byte-vector (f key (byte-vector->integer (pkcs1-pad msg)))))
((string? msg) (convert-plain f key (string->byte-vector msg)))
(else (f key msg)))))
(convert-cipher (lambda (f key cipher)
(cond
((byte-vector? cipher)
(pkcs1-unpad (integer->byte-vector (f key (byte-vector->integer cipher)))))
((string? cipher) (convert-cipher f key (string->byte-vector cipher)))
(else (f key cipher)))))
(encrypt (lambda (pub-key msg)
"Encrypts <par>msg</par> for the given public key <par>pub-key</par>.
<par>msg</par> may be an integer or bytevector, in which case the
result is of the same type, or a string, in which case the string
is first coerced to a utf8 encoded bytevector.
params:
- pub-key: the given RSA key
- msg: the message to encrypt
complexity: O(n)
returns: the cyphertext"
(if (not (rsa:key-e pub-key))
(error "can't encrypt without a public key" pub-key)
(convert-plain encrypt-integer pub-key msg))))
(decrypt (lambda (priv-key cipher)
"Decrypts cipher <par>using</par> the given private key <par>priv-key</par>.
<par>cipher</par> may be an integer or bytevector, in which case the
result is of the same type, or a string, in which case the string
is first coerced to a utf8 encoded bytevector.
params:
- priv-key: the given RSA key
- cipher: the ciphertext to decrypt
complexity: O(n)
returns: the decrypted message"
(if (not (rsa:key-d priv-key))
(error "can't decrypt without a private key" priv-key)
(convert-cipher decrypt-integer priv-key cipher))))
(sign (lambda (priv-key msg)
"Signs <par>msg</par> using the given private key <par>priv-key</par>.
<par>msg</par> may be an integer or bytevector, in which case the
result is of the same type, or a string, in which case the string
is first coerced to a utf8 encoded bytevector.
params:
params:
- priv-key: the given RSA key
- cipher: the ciphertext to decrypt
complexity: O(n)
returns: the signed message"
(if (not (rsa:key-d priv-key))
(error "can't sign without a private key" priv-key)
(convert-plain decrypt-integer priv-key msg))))
(verify (lambda (pub-key sig)
"Returns the verified (decrypted) message for the signature <par>sig</par>.
params:
- pub-key: the given RSA key
- sig: the given signature
complexity: O(n)
returns: the decrypted/verified message"
(if (not (rsa:key-e pub-key))
(error "can't verify without a public key" pub-key)
(convert-cipher encrypt-integer pub-key sig))))
(verify? (lambda (pub-key msg sig)
"Returns true iff <par>sig</par> is a valid signature of <par>msg</par> for
the given public key <par>pub-key</par>.
params:
- pub-key: the given RSA key
- msg: the message to verify
- sig: the signature
complexity: O(n)
returns: a boolean"
(equal? (if (string? msg) (string->utf8 msg) msg)
(verify pub-key sig)))))