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