1
2(********************************************************************)
3(*                                                                  *)
4(*  pkcs1.s7i     RSA public-key cryptography standard #1 support.  *)
5(*  Copyright (C) 2013 - 2015  Thomas Mertes                        *)
6(*                                                                  *)
7(*  This file is part of the Seed7 Runtime Library.                 *)
8(*                                                                  *)
9(*  The Seed7 Runtime Library is free software; you can             *)
10(*  redistribute it and/or modify it under the terms of the GNU     *)
11(*  Lesser General Public License as published by the Free Software *)
12(*  Foundation; either version 2.1 of the License, or (at your      *)
13(*  option) any later version.                                      *)
14(*                                                                  *)
15(*  The Seed7 Runtime Library is distributed in the hope that it    *)
16(*  will be useful, but WITHOUT ANY WARRANTY; without even the      *)
17(*  implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR *)
18(*  PURPOSE.  See the GNU Lesser General Public License for more    *)
19(*  details.                                                        *)
20(*                                                                  *)
21(*  You should have received a copy of the GNU Lesser General       *)
22(*  Public License along with this program; if not, write to the    *)
23(*  Free Software Foundation, Inc., 51 Franklin Street,             *)
24(*  Fifth Floor, Boston, MA  02110-1301, USA.                       *)
25(*                                                                  *)
26(********************************************************************)
27
28
29include "bytedata.s7i";
30include "msgdigest.s7i";
31include "hmac.s7i";
32
33
34const type: rsaKey is new struct
35    var bigInteger: modulus  is 0_;  # n
36    var bigInteger: exponent is 0_;  # public: e, private: d
37    var integer: modulusLen is 0;    # k denotes the length in octets of the RSA modulus n.
38  end struct;
39
40# n  The RSA modulus, a positive integer
41# e  The RSA public exponent, a positive integer
42# d  The RSA private exponent, a positive integer
43
44
45(**
46 *  Type to describe a pair of RSA keys (private key and public key).
47 *)
48const type: rsaKeyPair is new struct
49    var rsaKey: publicKey is rsaKey.value;
50    var rsaKey: privateKey is rsaKey.value;
51  end struct;
52
53
54const func rsaKey: rsaKey (in bigInteger: modulus, in bigInteger: exponent) is func
55  result
56    var rsaKey: aKey is rsaKey.value;
57  begin
58    aKey.modulus := modulus;
59    aKey.exponent := exponent;
60    # writeln("bitLength(modulus): " <& bitLength(modulus));
61    aKey.modulusLen := pred(bitLength(modulus)) mdiv 8 + 1;
62    # writeln("modulusLen: " <& aKey.modulusLen);
63  end func;
64
65
66const func string: literal (in rsaKey: aKey) is
67  return "rsaKey(" <& aKey.modulus <& "_, " <&
68                      aKey.exponent <& "_)";
69
70
71const func rsaKeyPair: rsaKeyPair (in rsaKey: publicKey, in rsaKey: privateKey) is func
72  result
73    var rsaKeyPair: aKeyPair is rsaKeyPair.value;
74  begin
75    aKeyPair.publicKey := publicKey;
76    aKeyPair.privateKey := privateKey;
77  end func;
78
79
80const func string: literal (in rsaKeyPair: aKeyPair) is
81  return "rsaKeyPair(" <& literal(aKeyPair.publicKey) <& ", " <&
82                          literal(aKeyPair.privateKey) <& ")";
83
84
85const rsaKeyPair: stdRsaKeyPair is rsaKeyPair(
86    rsaKey(24879323998282062445559239376138627672251789324639932255760945448830518737190739384640974288529252990629999154107088744522353230056093690582734642121734324688998783187082956551041534076711835155928707829063256162504640988273175086145464721272768789724523888480071692284791450208699922038033347977493657812564984507698611204922456314960345290535639893058558496084848086047929946200129560169331200998008734185791703119413114661834404705794384334141821974803140053993070324815699000969159963681641979473501237806530434553142494356819076895646395931159040168081404923835928757739530245969373700156294158081824152324534461_,
87           65537_),
88    rsaKey(24879323998282062445559239376138627672251789324639932255760945448830518737190739384640974288529252990629999154107088744522353230056093690582734642121734324688998783187082956551041534076711835155928707829063256162504640988273175086145464721272768789724523888480071692284791450208699922038033347977493657812564984507698611204922456314960345290535639893058558496084848086047929946200129560169331200998008734185791703119413114661834404705794384334141821974803140053993070324815699000969159963681641979473501237806530434553142494356819076895646395931159040168081404923835928757739530245969373700156294158081824152324534461_,
89           13088626772857606374994147660260732180049394881287449598152583688371128141673593733366670911392214849793873855002581835202125435492530910232563666189681493608607352285338757891981781465383991523965240833886856981107389901791087944521771406381777047043992471840577258748417529339084119078189629851351546974405368864243464335513384244053469543096484265307474308910575994412661107393352461835904945528516443603610779331782072425524550819129133717693244132152897414694106718806022258591593987246936431975237846760817339494993145835504324086601210101710742420357193277289205188098444617372451223173144294880256099265243073_));
90
91
92const func boolean: isProbablyPrime (in bigInteger: primeCandidate, in var integer: count) is func
93  result
94    var boolean: isProbablyPrime is TRUE;
95  local
96    var bigInteger: aRandomNumber is 0_;
97  begin
98    while isProbablyPrime and count > 0 do
99      aRandomNumber := rand(1_, pred(primeCandidate));
100      isProbablyPrime := modPow(aRandomNumber, pred(primeCandidate), primeCandidate) = 1_;
101      decr(count);
102    end while;
103    # writeln(count);
104  end func;
105
106
107const func bigInteger: getProbablyPrime (in integer: binDigits, in integer: count) is func
108  result
109    var bigInteger: probablyPrime is 0_;
110  begin
111    probablyPrime := rand(0_, 2_**binDigits - 1_);
112    if not odd(probablyPrime) then
113      incr(probablyPrime);
114    end if;
115    while not isProbablyPrime(probablyPrime, count) do
116      # write(".");
117      # flush(OUT);
118      probablyPrime +:= 2_;
119    end while;
120    # writeln;
121  end func;
122
123
124(**
125 *  Generate a new RSA keyPair (private key and public key).
126 *)
127const func rsaKeyPair: genRsaKeyPair (in integer: keyLength, in bigInteger: exponent) is func
128  result
129    var rsaKeyPair: keyPair is rsaKeyPair.value;
130  local
131    const integer: numTests is 10;
132    var bigInteger: p is 0_;
133    var bigInteger: q is 0_;
134    var bigInteger: modulus is 0_;         # n
135    var bigInteger: phiOfModulus is 0_;    # φ(n)
136    var bigInteger: privateExponent is 0_; # d
137  begin
138    p := getProbablyPrime(keyLength mdiv 2, numTests);
139    q := getProbablyPrime(keyLength mdiv 2, numTests);
140    modulus := p * q;
141    phiOfModulus := pred(p) * pred(q);
142    keyPair.publicKey := rsaKey(modulus, exponent);
143    keyPair.privateKey := rsaKey(modulus, modInverse(exponent, phiOfModulus));
144  end func;
145
146
147(**
148 *  Convert a nonnegative [[bigint|bigInteger]] to an octet [[string]] of a specified length (I2OSP).
149 *  @return an octet [[string]] with the big-endian representation.
150 *  @exception RANGE_ERROR If the result does not fit into ''length''.
151 *)
152const func string: int2Octets (in bigInteger: number, in integer: length) is
153  return bytes(number, UNSIGNED, BE, length);
154
155
156(**
157 *  Convert an octet [[string]] to a nonnegative [[bigint|bigInteger]] (OS2IP).
158 *  @return a nonnegative bigInteger created from the big-endian bytes.
159 *  @exception RANGE_ERROR If characters beyond '\255;' are present.
160 *)
161const func bigInteger: octets2int (in string: stri) is
162  return bytes2BigInt(stri, UNSIGNED, BE);
163
164
165(**
166 *  Encodes a [[string]] with the EME-OAEP encoding.
167 *  @return the EME-OAEP encoded [[string]].
168 *)
169const func string: emeOaepEncoding (in string: message, in string: label, in integer: modulusLen) is func
170  result
171    var string: encodedMessage is "";
172  local
173    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
174    var string: lHash is "";
175    var string: ps is "";
176    var string: db is "";
177    var string: seed is "";
178    var string: dbMask is "";
179    var string: maskedDb is "";
180    var string: seedMask is "";
181    var string: maskedSeed is "";
182  begin
183    lHash := sha1(label);
184    ps := "\0;" mult modulusLen - length(message) - 2 * hLen - 2;
185    db := lHash & ps & "\1;" & message;
186    # Generate a random octet string seed of length hLen.
187    seed := int2Octets(rand(0_, 2_ ** (hLen * 8) - 1_), hLen);
188    dbMask := mgf1Sha1(seed, modulusLen - hLen - 1);
189    maskedDb := db >< dbMask;
190    seedMask := mgf1Sha1(maskedDb, hLen);
191    maskedSeed := seed >< seedMask;
192    encodedMessage := "\0;" & maskedSeed & maskedDb;
193  end func;
194
195
196(**
197 *  Decodes an EME-OAEP encoded [[string]].
198 *  @return the decoded string.
199 *  @exception RANGE_ERROR If ''encodedMessage'' is not in the
200 *                         EME-OAEP format.
201 *)
202const func string: emeOaepDecoding (in string: encodedMessage, in string: label, in integer: modulusLen) is func
203  result
204    var string: message is "";
205  local
206    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
207    var string: y is "";
208    var string: maskedSeed is "";
209    var string: maskedDb is "";
210    var string: seedMask is "";
211    var string: seed is "";
212    var string: dbMask is "";
213    var string: db is "";
214    var string: lHash is "";
215    var integer: pos is 0;
216  begin
217    y := encodedMessage[1 len 1];
218    maskedSeed := encodedMessage[2 len hLen];
219    maskedDb := encodedMessage[hLen + 2 ..];  # length: modulusLen - hLen - 1;
220    seedMask := mgf1Sha1(maskedDb, hLen);
221    seed := maskedSeed >< seedMask;
222    dbMask := mgf1Sha1(seed, modulusLen - hLen - 1);
223    db := maskedDb >< dbMask;
224    lHash := db[.. hLen];
225    # writeln("lHash: " <& hex(lHash));
226    # writeln("raw: " <& literal(db));
227    if lHash <> sha1(label) then
228      raise RANGE_ERROR;
229    end if;
230    pos := succ(hLen);
231    while db[pos] <> '\1;' do
232      incr(pos);
233    end while;
234    message := db[succ(pos) ..];
235  end func;
236
237
238(**
239 *  Encodes a [[string]] with the EME-PKCS1-v1_5 encoding.
240 *  @return the EME-PKCS1-v1_5 encoded [[string]].
241 *)
242const func string: emePkcs1V15Encoding (in string: message, in integer: modulusLen) is func
243  result
244    var string: encodedMessage is "";
245  local
246    var integer: pos is 0;
247    var string: ps is "";
248  begin
249    for pos range 1 to modulusLen - length(message) - 3 do
250      ps &:= rand('\1;', '\255;');
251    end for;
252    encodedMessage := "\0;\2;" & ps & "\0;" & message;
253  end func;
254
255
256(**
257 *  Decodes an EME-PKCS1-v1_5 encoded [[string]].
258 *  @return the decoded string.
259 *  @exception RANGE_ERROR If ''encodedMessage'' is not in the
260 *                         EME-PKCS1-v1_5 format.
261 *)
262const func string: emePkcs1V15Decoding (in string: encodedMessage, in integer: modulusLen) is func
263  result
264    var string: message is "";
265  local
266    var integer: pos is 0;
267  begin
268    if not startsWith(encodedMessage, "\0;\2;") then
269      # writeln("encodedMessage: " <& hex(encodedMessage));
270      raise RANGE_ERROR;
271    else
272      pos := pos(encodedMessage[3 ..], '\0;');
273      if pos = 0 then
274        raise RANGE_ERROR;
275      else
276        message := encodedMessage[pos + 3 ..];
277      end if;
278    end if;
279  end func;
280
281
282(**
283 *  Encodes a [[string]] with the EMSA-PKCS1-v1_5 encoding.
284 *  @return the EMSA-PKCS1-v1_5 encoded [[string]].
285 *)
286const func string: emsaPkcs1V15Encoding (in string: message, in integer: modulusLen) is func
287  result
288    var string: encodedMessage is "";
289  local
290    var string: ps is "";
291  begin
292    ps := "\255;" mult modulusLen - length(message) - 3;
293    encodedMessage := "\0;\1;" & ps & "\0;" & message;
294  end func;
295
296
297(**
298 *  Decodes an EMSA-PKCS1-v1_5 encoded [[string]].
299 *  @return the decoded string.
300 *  @exception RANGE_ERROR If ''encodedMessage'' is not in the
301 *                         EME-PKCS1-v1_5 format.
302 *)
303const func string: emsaPkcs1V15Decoding (in string: encodedMessage) is func
304  result
305    var string: message is "";
306  local
307    var integer: pos is 0;
308  begin
309    if not startsWith(encodedMessage, "\0;\1;") then
310      # writeln("encodedMessage: " <& hex(encodedMessage));
311      raise RANGE_ERROR;
312    else
313      pos := pos(encodedMessage[3 ..], '\0;');
314      if pos < 9 or encodedMessage[3 len pred(pos)] <> "\255;" mult pred(pos) then
315        raise RANGE_ERROR;
316      else
317        message := encodedMessage[pos + 3 ..];
318      end if;
319    end if;
320  end func;
321
322
323(**
324 *  Encrypts a [[bigint|bigInteger]] with the RSAES encryption.
325 *  @return the RSAES encrypted [[bigint|bigInteger]].
326 *  @exception RANGE_ERROR If ''message'' is too big for the
327 *                         RSAEP encryption.
328 *)
329const func bigInteger: rsaEncrypt (in rsaKey: encryptionKey, in bigInteger: message) is func
330  result
331    var bigInteger: ciphertext is 0_;
332  begin
333    if message >= encryptionKey.modulus then
334      raise RANGE_ERROR;
335    else
336      ciphertext := modPow(message, encryptionKey.exponent, encryptionKey.modulus);
337    end if;
338  end func;
339
340
341(**
342 *  Decrypts a [[bigint|bigInteger]] with the RSADP decryption.
343 *  @return the RSADP decrypted [[bigint|bigInteger]].
344 *  @exception RANGE_ERROR If ''ciphertext'' is too big for the
345 *                         RSADP decryption.
346 *)
347const func bigInteger: rsaDecrypt (in rsaKey: decryptionKey, in bigInteger: ciphertext) is func
348  result
349    var bigInteger: message is 0_;
350  begin
351    # writeln("rsaDecrypt: modulus    = " <& decryptionKey.modulus radix 16);
352    # writeln("rsaDecrypt: exponent   = " <& decryptionKey.exponent radix 16);
353    # writeln("rsaDecrypt: ciphertext = " <& ciphertext radix 16);
354    if ciphertext >= decryptionKey.modulus then
355      raise RANGE_ERROR;
356    else
357      message := modPow(ciphertext, decryptionKey.exponent, decryptionKey.modulus);
358    end if;
359  end func;
360
361
362(**
363 *  Encrypts a [[string]] of bytes with the RSAES-OAEP encryption.
364 *  @return the RSAES-OAEP encrypted [[string]] of bytes.
365 *  @exception RANGE_ERROR If the length of the ''message'' is too long
366 *                         to be encrypted.
367 *  @exception RANGE_ERROR If ''message'' contains characters beyond '\255;'.
368 *)
369const func string: rsaesOaepEncrypt (in rsaKey: encryptionKey, in string: message,
370    in string: label) is func
371  result
372    var string: encryptedMessage is "";
373  local
374    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
375    var string: encodedMessage is "";
376  begin
377    if length(message) > encryptionKey.modulusLen - 2 * hLen - 2 then
378      raise RANGE_ERROR;
379    else
380      encodedMessage := emeOaepEncoding(message, label, encryptionKey.modulusLen);
381      encryptedMessage := int2Octets(rsaEncrypt(encryptionKey, octets2int(encodedMessage)),
382                                     encryptionKey.modulusLen);
383    end if;
384  end func;
385
386
387(**
388 *  Decrypts a [[string]] of bytes with the RSAES-OAEP decryption.
389 *  @return the RSAES-OAEP decrypted [[string]] of bytes.
390 *  @exception RANGE_ERROR If the length of the ''ciphertext'' is too long
391 *                         to be decrypted.
392 *  @exception RANGE_ERROR If ''ciphertext'' contains characters beyond '\255;'.
393 *)
394const func string: rsaesOaepDecrypt (in rsaKey: decryptionKey, in string: ciphertext,
395    in string: label) is func
396  result
397    var string: message is "";
398  local
399    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
400    var string: encodedMessage is "";
401  begin
402    if length(ciphertext) <> decryptionKey.modulusLen or
403        decryptionKey.modulusLen < 2 * hLen + 2 then
404      # writeln("length(ciphertext): " <& length(ciphertext));
405      # writeln("modulusLen: " <& decryptionKey.modulusLen);
406      raise RANGE_ERROR;
407    else
408      encodedMessage := int2Octets(rsaDecrypt(decryptionKey, octets2int(ciphertext)),
409                                   decryptionKey.modulusLen);
410      message := emeOaepDecoding(encodedMessage, label, decryptionKey.modulusLen);
411    end if;
412  end func;
413
414
415(**
416 *  Encrypts a [[string]] of bytes with the RSAES-PKCS1-V1_5 encryption.
417 *  @return the RSAES-PKCS1-V1_5 encrypted [[string]] of bytes.
418 *  @exception RANGE_ERROR If the length of the ''message'' is too long
419 *                         to be encrypted.
420 *  @exception RANGE_ERROR If ''message'' contains characters beyond '\255;'.
421 *)
422const func string: rsaesPkcs1V15Encrypt (in rsaKey: encryptionKey, in string: message) is func
423  result
424    var string: encryptedMessage is "";
425  local
426    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
427    var string: encodedMessage is "";
428  begin
429    if length(message) > encryptionKey.modulusLen - 2 * hLen - 2 then
430      # writeln("length(message): " <& length(message));
431      # writeln("modulusLen: " <& encryptionKey.modulusLen);
432      raise RANGE_ERROR;
433    else
434      encodedMessage := emePkcs1V15Encoding(message, encryptionKey.modulusLen);
435      encryptedMessage := int2Octets(rsaEncrypt(encryptionKey, octets2int(encodedMessage)),
436                                     encryptionKey.modulusLen);
437    end if;
438  end func;
439
440
441(**
442 *  Decrypts a [[string]] of bytes with the RSAES-PKCS1-V1_5 decryption.
443 *  @return the RSAES-PKCS1-V1_5 decrypted [[string]] of bytes.
444 *  @exception RANGE_ERROR If the length of the ''ciphertext'' is too long
445 *                         to be decrypted.
446 *  @exception RANGE_ERROR If ''ciphertext'' contains characters beyond '\255;'.
447 *)
448const func string: rsaesPkcs1V15Decrypt (in rsaKey: decryptionKey, in string: ciphertext) is func
449  result
450    var string: message is "";
451  local
452    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
453    var string: encodedMessage is "";
454  begin
455    if length(ciphertext) <> decryptionKey.modulusLen or
456        decryptionKey.modulusLen < 2 * hLen + 2 then
457      # writeln("length(ciphertext): " <& length(ciphertext));
458      # writeln("modulusLen: " <& decryptionKey.modulusLen);
459      raise RANGE_ERROR;
460    else
461      encodedMessage := int2Octets(rsaDecrypt(decryptionKey, octets2int(ciphertext)),
462                                   decryptionKey.modulusLen);
463      message := emePkcs1V15Decoding(encodedMessage, decryptionKey.modulusLen);
464    end if;
465  end func;
466
467
468(**
469 *  Encrypts a [[string]] of bytes with the RSASSA-PKCS1-V1_5 encryption.
470 *  @return the RSASSA-PKCS1-V1_5 encrypted [[string]] of bytes.
471 *  @exception RANGE_ERROR If the length of the ''message'' is too long
472 *                         to be encrypted.
473 *  @exception RANGE_ERROR If ''message'' contains characters beyond '\255;'.
474 *)
475const func string: rsassaPkcs1V15Encrypt (in rsaKey: encryptionKey, in string: message) is func
476  result
477    var string: encryptedMessage is "";
478  local
479    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
480    var string: encodedMessage is "";
481  begin
482    if length(message) > encryptionKey.modulusLen - 2 * hLen - 2 then
483      # writeln("length(message): " <& length(message));
484      # writeln("modulusLen: " <& encryptionKey.modulusLen);
485      raise RANGE_ERROR;
486    else
487      encodedMessage := emsaPkcs1V15Encoding(message, encryptionKey.modulusLen);
488      encryptedMessage := int2Octets(rsaEncrypt(encryptionKey, octets2int(encodedMessage)),
489                                     encryptionKey.modulusLen);
490    end if;
491  end func;
492
493
494(**
495 *  Decrypts a [[string]] of bytes with the RSASSA-PKCS1-V1_5 decryption.
496 *  @return the RSASSA-PKCS1-V1_5 decrypted [[string]] of bytes.
497 *  @exception RANGE_ERROR If the length of the ''ciphertext'' is too long
498 *                         to be decrypted.
499 *  @exception RANGE_ERROR If ''ciphertext'' contains characters beyond '\255;'.
500 *)
501const func string: rsassaPkcs1V15Decrypt (in rsaKey: decryptionKey, in string: ciphertext) is func
502  result
503    var string: message is "";
504  local
505    const integer: hLen is 20;  # Length (in bytes) of the sha1 output.
506    var string: encodedMessage is "";
507  begin
508    if length(ciphertext) <> decryptionKey.modulusLen or
509        decryptionKey.modulusLen < 2 * hLen + 2 then
510      # writeln("length(ciphertext): " <& length(ciphertext));
511      # writeln("modulusLen: " <& decryptionKey.modulusLen);
512      raise RANGE_ERROR;
513    else
514      encodedMessage := int2Octets(rsaDecrypt(decryptionKey, octets2int(ciphertext)),
515                                   decryptionKey.modulusLen);
516      message := emsaPkcs1V15Decoding(encodedMessage);
517    end if;
518  end func;
519