File: rfc2437.txt

package info (click to toggle)
doc-rfc 20181229-2
  • links: PTS, VCS
  • area: non-free
  • in suites: buster
  • size: 570,944 kB
  • sloc: xml: 285,646; sh: 107; python: 90; perl: 42; makefile: 14
file content (2187 lines) | stat: -rw-r--r-- 73,529 bytes parent folder | download | duplicates (5)
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187






Network Working Group                                         B. Kaliski
Request for Comments: 2437                                    J. Staddon
Obsoletes: 2313                                         RSA Laboratories
Category: Informational                                     October 1998


                PKCS #1: RSA Cryptography Specifications
                              Version 2.0

Status of this Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (1998).  All Rights Reserved.

Table of Contents

   1.       Introduction.....................................2
   1.1      Overview.........................................3
   2.       Notation.........................................3
   3.       Key types........................................5
   3.1      RSA public key...................................5
   3.2      RSA private key..................................5
   4.       Data conversion primitives.......................6
   4.1      I2OSP............................................6
   4.2      OS2IP............................................7
   5.       Cryptographic primitives.........................8
   5.1      Encryption and decryption primitives.............8
   5.1.1    RSAEP............................................8
   5.1.2    RSADP............................................9
   5.2      Signature and verification primitives...........10
   5.2.1    RSASP1..........................................10
   5.2.2    RSAVP1..........................................11
   6.       Overview of schemes.............................11
   7.       Encryption schemes..............................12
   7.1      RSAES-OAEP......................................13
   7.1.1    Encryption operation............................13
   7.1.2    Decryption operation............................14
   7.2      RSAES-PKCS1-v1_5................................15
   7.2.1    Encryption operation............................17
   7.2.2    Decryption operation............................17
   8.       Signature schemes with appendix.................18
   8.1      RSASSA-PKCS1-v1_5...............................19
   8.1.1    Signature generation operation..................20



Kaliski & Staddon            Informational                      [Page 1]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   8.1.2    Signature verification operation................21
   9.       Encoding methods................................22
   9.1      Encoding methods for encryption.................22
   9.1.1    EME-OAEP........................................22
   9.1.2    EME-PKCS1-v1_5..................................24
   9.2      Encoding methods for signatures with appendix...26
   9.2.1    EMSA-PKCS1-v1_5.................................26
   10.      Auxiliary Functions.............................27
   10.1     Hash Functions..................................27
   10.2     Mask Generation Functions.......................28
   10.2.1   MGF1............................................28
   11.      ASN.1 syntax....................................29
   11.1     Key representation..............................29
   11.1.1   Public-key syntax...............................30
   11.1.2   Private-key syntax..............................30
   11.2     Scheme identification...........................31
   11.2.1   Syntax for RSAES-OAEP...........................31
   11.2.2   Syntax for RSAES-PKCS1-v1_5.....................32
   11.2.3   Syntax for RSASSA-PKCS1-v1_5....................33
   12       Patent Statement................................33
   12.1     Patent statement for the RSA algorithm..........34
   13.      Revision history................................35
   14.      References......................................35
            Security Considerations.........................37
            Acknowledgements................................37
            Authors' Addresses..............................38
            Full Copyright Statement........................39

1. Introduction

   This memo is the successor to RFC 2313. This document provides
   recommendations for the implementation of public-key cryptography
   based on the RSA algorithm [18], covering the following aspects:

      -cryptographic primitives
      -encryption schemes
      -signature schemes with appendix
      -ASN.1 syntax for representing keys and for identifying the
       schemes

   The recommendations are intended for general application within
   computer and communications systems, and as such include a fair
   amount of flexibility. It is expected that application standards
   based on these specifications may include additional constraints. The
   recommendations are intended to be compatible with draft standards
   currently being developed by the ANSI X9F1 [1] and IEEE P1363 working
   groups [14].  This document supersedes PKCS #1 version 1.5 [20].




Kaliski & Staddon            Informational                      [Page 2]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Editor's note. It is expected that subsequent versions of PKCS #1 may
   cover other aspects of the RSA algorithm such as key size, key
   generation, key validation, and signature schemes with message
   recovery.

1.1 Overview

   The organization of this document is as follows:

      -Section 1 is an introduction.
      -Section 2 defines some notation used in this document.
      -Section 3 defines the RSA public and private key types.
      -Sections 4 and 5 define several primitives, or basic mathematical
       operations. Data conversion primitives are in Section 4, and
       cryptographic primitives (encryption-decryption,
       signature-verification) are in Section 5.
      -Section 6, 7 and 8 deal with the encryption and signature schemes
       in this document. Section 6 gives an overview. Section 7 defines
       an OAEP-based [2] encryption scheme along with the method found
       in PKCS #1 v1.5.  Section 8 defines a signature scheme with
       appendix; the method is identical to that of PKCS #1 v1.5.
      -Section 9 defines the encoding methods for the encryption and
       signature schemes in Sections 7 and 8.
      -Section 10 defines the hash functions and the mask generation
       function used in this document.
      -Section 11 defines the ASN.1 syntax for the keys defined in
       Section 3 and the schemes gives in Sections 7 and 8.
      -Section 12 outlines the revision history of PKCS #1.
      -Section 13 contains references to other publications and
       standards.

2. Notation

   (n, e)        RSA public key

   c             ciphertext representative, an integer between 0 and n-1

   C             ciphertext, an octet string

   d             private exponent

   dP            p's exponent, a positive integer such that:
                  e(dP)\equiv 1 (mod(p-1))

   dQ            q's exponent, a positive integer such that:
                  e(dQ)\equiv 1 (mod(q-1))

   e             public exponent



Kaliski & Staddon            Informational                      [Page 3]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   EM            encoded message, an octet string

   emLen         intended length in octets of an encoded message

   H             hash value, an output of Hash

   Hash          hash function

   hLen          output length in octets of hash function Hash

   K             RSA private key

   k             length in octets of the modulus

   l             intended length of octet string

   lcm(.,.)      least common multiple of two
                 nonnegative integers

   m             message representative, an integer between
                 0 and n-1

   M             message, an octet string

   MGF           mask generation function

   n             modulus

   P             encoding parameters, an octet string

   p,q           prime factors of the modulus

   qInv          CRT coefficient, a positive integer less
                 than p such: q(qInv)\equiv 1 (mod p)

   s             signature representative, an integer
                 between 0 and n-1

   S             signature, an octet string

   x             a nonnegative integer

   X             an octet string corresponding to x

   \xor          bitwise exclusive-or of two octet strings

   \lambda(n)    lcm(p-1, q-1), where n = pq




Kaliski & Staddon            Informational                      [Page 4]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   ||            concatenation operator

   ||.||         octet length operator

3. Key types

   Two key types are employed in the primitives and schemes defined in
   this document: RSA public key and RSA private key. Together, an RSA
   public key and an RSA private key form an RSA key pair.

3.1 RSA public key

   For the purposes of this document, an RSA public key consists of two
   components:

   n, the modulus, a nonnegative integer
   e, the public exponent, a nonnegative integer

   In a valid RSA public key, the modulus n is a product of two odd
   primes p and q, and the public exponent e is an integer between 3 and
   n-1 satisfying gcd (e, \lambda(n)) = 1, where \lambda(n) = lcm (p-
   1,q-1).  A recommended syntax for interchanging RSA public keys
   between implementations is given in Section 11.1.1; an
   implementation's internal representation may differ.

3.2 RSA private key

   For the purposes of this document, an RSA private key may have either
   of two representations.

   1. The first representation consists of the pair (n, d), where the
   components have the following meanings:

   n, the modulus, a nonnegative integer
   d, the private exponent, a nonnegative integer

   2. The second representation consists of a quintuple (p, q, dP, dQ,
   qInv), where the components have the following meanings:

   p, the first factor, a nonnegative integer
   q, the second factor, a nonnegative integer
   dP, the first factor's exponent, a nonnegative integer
   dQ, the second factor's exponent, a nonnegative integer
   qInv, the CRT coefficient, a nonnegative integer

   In a valid RSA private key with the first representation, the modulus
   n is the same as in the corresponding public key and is the product
   of two odd primes p and q, and the private exponent d is a positive



Kaliski & Staddon            Informational                      [Page 5]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   integer less than n satisfying:

   ed \equiv 1 (mod \lambda(n))

   where e is the corresponding public exponent and \lambda(n) is as
   defined above.

   In a valid RSA private key with the second representation, the two
   factors p and q are the prime factors of the modulus n, the exponents
   dP and dQ are positive integers less than p and q respectively
   satisfying

   e(dP)\equiv 1(mod(p-1))
   e(dQ)\equiv 1(mod(q-1)),

   and the CRT coefficient qInv is a positive integer less than p
   satisfying:

   q(qInv)\equiv 1 (mod p).

   A recommended syntax for interchanging RSA private keys between
   implementations, which includes components from both representations,
   is given in Section 11.1.2; an implementation's internal
   representation may differ.

4. Data conversion primitives

   Two data conversion primitives are employed in the schemes defined in
   this document:

   I2OSP: Integer-to-Octet-String primitive
   OS2IP: Octet-String-to-Integer primitive

   For the purposes of this document, and consistent with ASN.1 syntax, an
   octet string is an ordered sequence of octets (eight-bit bytes). The
   sequence is indexed from first (conventionally, leftmost) to last
   (rightmost). For purposes of conversion to and from integers, the first
   octet is considered the most significant in the following conversion
   primitives

4.1 I2OSP

   I2OSP converts a nonnegative integer to an octet string of a specified
   length.

   I2OSP (x, l)





Kaliski & Staddon            Informational                      [Page 6]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Input:
   x         nonnegative integer to be converted
   l         intended length of the resulting octet string

   Output:
   X         corresponding octet string of length l; or
             "integer too large"

   Steps:

   1. If x>=256^l, output "integer too large" and stop.

   2. Write the integer x in its unique l-digit representation base 256:

   x = x_{l-1}256^{l-1} + x_{l-2}256^{l-2} +... + x_1 256 + x_0

   where 0 <= x_i < 256 (note that one or more leading digits will be
   zero if x < 256^{l-1}).

   3. Let the octet X_i have the value x_{l-i} for 1 <= i <= l.  Output
   the octet string:

   X = X_1 X_2 ... X_l.

4.2 OS2IP

   OS2IP converts an octet string to a nonnegative integer.

   OS2IP (X)

   Input:
   X         octet string to be converted

   Output:
   x         corresponding nonnegative integer

   Steps:

   1. Let X_1 X_2 ... X_l  be the octets of X from first to last, and
   let x{l-i} have value X_i for 1<= i <= l.

   2. Let x = x{l-1} 256^{l-1} + x_{l-2} 256^{l-2} +...+ x_1 256 + x_0.

   3. Output x.







Kaliski & Staddon            Informational                      [Page 7]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


5. Cryptographic primitives

   Cryptographic primitives are basic mathematical operations on which
   cryptographic schemes can be built. They are intended for
   implementation in hardware or as software modules, and are not
   intended to provide security apart from a scheme.

   Four types of primitive are specified in this document, organized in
   pairs: encryption and decryption; and signature and verification.

   The specifications of the primitives assume that certain conditions
   are met by the inputs, in particular that public and private keys are
   valid.

5.1 Encryption and decryption primitives

   An encryption primitive produces a ciphertext representative from a
   message representative under the control of a public key, and a
   decryption primitive recovers the message representative from the
   ciphertext representative under the control of the corresponding
   private key.

   One pair of encryption and decryption primitives is employed in the
   encryption schemes defined in this document and is specified here:
   RSAEP/RSADP. RSAEP and RSADP involve the same mathematical operation,
   with different keys as input.

   The primitives defined here are the same as in the draft IEEE P1363
   and are compatible with PKCS #1 v1.5.

   The main mathematical operation in each primitive is exponentiation.

5.1.1 RSAEP

   RSAEP((n, e), m)

   Input:
   (n, e)    RSA public key
   m         message representative, an integer between 0 and n-1

   Output:
   c         ciphertext representative, an integer between 0 and n-1;
             or "message representative out of range"

   Assumptions: public key (n, e) is valid

   Steps:




Kaliski & Staddon            Informational                      [Page 8]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   1. If the message representative m is not between 0 and n-1, output
   message representative out of range and stop.

   2. Let c = m^e mod n.

   3. Output c.

5.1.2 RSADP

   RSADP (K, c)

   Input:

   K         RSA private key, where K has one of the following forms
                 -a pair (n, d)
                 -a quintuple (p, q, dP, dQ, qInv)
   c         ciphertext representative, an integer between 0 and n-1

   Output:
   m         message representative, an integer between 0 and n-1; or
             "ciphertext representative out of range"

   Assumptions: private key K is valid

   Steps:

   1. If the ciphertext representative c is not between 0 and n-1,
   output "ciphertext representative out of range" and stop.

   2. If the first form (n, d) of K is used:

   2.1 Let m = c^d mod n.          Else, if the second form (p, q, dP,
   dQ, qInv) of K is used:

   2.2 Let m_1 = c^dP mod p.

   2.3 Let m_2 = c^dQ mod q.

   2.4 Let h = qInv ( m_1 - m_2 ) mod p.

   2.5 Let m = m_2 + hq.

   3. Output m.








Kaliski & Staddon            Informational                      [Page 9]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


5.2 Signature and verification primitives

   A signature primitive produces a signature representative from a
   message representative under the control of a private key, and a
   verification primitive recovers the message representative from the
   signature representative under the control of the corresponding
   public key. One pair of signature and verification primitives is
   employed in the signature schemes defined in this document and is
   specified here: RSASP1/RSAVP1.

   The primitives defined here are the same as in the draft IEEE P1363
   and are compatible with PKCS #1 v1.5.

   The main mathematical operation in each primitive is exponentiation,
   as in the encryption and decryption primitives of Section 5.1. RSASP1
   and RSAVP1 are the same as RSADP and RSAEP except for the names of
   their input and output arguments; they are distinguished as they are
   intended for different purposes.

5.2.1 RSASP1

   RSASP1 (K, m)

   Input:
   K             RSA private key, where K has one of the following
                 forms:
                    -a pair (n, d)
                    -a quintuple (p, q, dP, dQ, qInv)

   m             message representative, an integer between 0 and n-1

   Output:
   s             signature representative, an integer between  0 and
                 n-1, or "message representative out of range"

   Assumptions:
   private key K is valid

   Steps:

   1. If the message representative m is not between 0 and n-1, output
   "message representative out of range" and stop.

   2. If the first form (n, d) of K is used:

   2.1 Let s = m^d mod n.          Else, if the second form (p, q, dP,
   dQ, qInv) of K is used:




Kaliski & Staddon            Informational                     [Page 10]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   2.2 Let s_1 = m^dP mod p.

   2.3 Let s_2 = m^dQ mod q.

   2.4 Let h = qInv ( s_1 - s_2 ) mod p.

   2.5 Let s = s_2 + hq.

   3. Output S.

5.2.2 RSAVP1

   RSAVP1 ((n, e), s)

   Input:
   (n, e)  RSA public key
   s       signature representative, an integer between 0 and n-1

   Output:
   m       message representative, an integer between 0 and n-1;
           or "invalid"

   Assumptions:
   public key (n, e) is valid

   Steps:

   1. If the signature representative s is not between 0 and n-1, output
   "invalid" and stop.

   2. Let m = s^e mod n.

   3. Output m.

6. Overview of schemes

   A scheme combines cryptographic primitives and other techniques to
   achieve a particular security goal. Two types of scheme are specified
   in this document: encryption schemes and signature schemes with
   appendix.

   The schemes specified in this document are limited in scope in that
   their operations consist only of steps to process data with a key,
   and do not include steps for obtaining or validating the key. Thus,
   in addition to the scheme operations, an application will typically
   include key management operations by which parties may select public
   and private keys for a scheme operation. The specific additional
   operations and other details are outside the scope of this document.



Kaliski & Staddon            Informational                     [Page 11]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   As was the case for the cryptographic primitives (Section 5), the
   specifications of scheme operations assume that certain conditions
   are met by the inputs, in particular that public and private keys are
   valid. The behavior of an implementation is thus unspecified when a
   key is invalid. The impact of such unspecified behavior depends on
   the application. Possible means of addressing key validation include
   explicit key validation by the application; key validation within the
   public-key infrastructure; and assignment of liability for operations
   performed with an invalid key to the party who generated the key.

7. Encryption schemes

   An encryption scheme consists of an encryption operation and a
   decryption operation, where the encryption operation produces a
   ciphertext from a message with a recipient's public key, and the
   decryption operation recovers the message from the ciphertext with
   the recipient's corresponding private key.

   An encryption scheme can be employed in a variety of applications. A
   typical application is a key establishment protocol, where the
   message contains key material to be delivered confidentially from one
   party to another. For instance, PKCS #7 [21] employs such a protocol
   to deliver a content-encryption key from a sender to a recipient; the
   encryption schemes defined here would be suitable key-encryption
   algorithms in that context.

   Two encryption schemes are specified in this document: RSAES-OAEP and
   RSAES-PKCS1-v1_5. RSAES-OAEP is recommended for new applications;
   RSAES-PKCS1-v1_5 is included only for compatibility with existing
   applications, and is not recommended for new applications.

   The encryption schemes given here follow a general model similar to
   that employed in IEEE P1363, by combining encryption and decryption
   primitives with an encoding method for encryption. The encryption
   operations apply a message encoding operation to a message to produce
   an encoded message, which is then converted to an integer message
   representative. An encryption primitive is applied to the message
   representative to produce the ciphertext. Reversing this, the
   decryption operations apply a decryption primitive to the ciphertext
   to recover a message representative, which is then converted to an
   octet string encoded message. A message decoding operation is applied
   to the encoded message to recover the message and verify the
   correctness of the decryption.








Kaliski & Staddon            Informational                     [Page 12]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


7.1 RSAES-OAEP

   RSAES-OAEP combines the RSAEP and RSADP primitives (Sections 5.1.1
   and 5.1.2) with the EME-OAEP encoding method (Section 9.1.1) EME-OAEP
   is based on the method found in [2]. It is compatible with the IFES
   scheme defined in the draft P1363 where the encryption and decryption
   primitives are IFEP-RSA and IFDP-RSA and the message encoding method
   is EME-OAEP. RSAES-OAEP can operate on messages of length up to k-2-
   2hLen octets, where hLen is the length of the hash function output
   for EME-OAEP and k is the length in octets of the recipient's RSA
   modulus.  Assuming that the hash function in EME-OAEP has appropriate
   properties, and the key size is sufficiently large, RSAEP-OAEP
   provides "plaintext-aware encryption," meaning that it is
   computationally infeasible to obtain full or partial information
   about a message from a ciphertext, and computationally infeasible to
   generate a valid ciphertext without knowing the corresponding
   message.  Therefore, a chosen-ciphertext attack is ineffective
   against a plaintext-aware encryption scheme such as RSAES-OAEP.

   Both the encryption and the decryption operations of RSAES-OAEP take
   the value of the parameter string P as input. In this version of PKCS
   #1, P is an octet string that is specified explicitly. See Section
   11.2.1 for the relevant ASN.1 syntax. We briefly note that to receive
   the full security benefit of RSAES-OAEP, it should not be used in a
   protocol involving RSAES-PKCS1-v1_5. It is possible that in a
   protocol on which both encryption schemes are present, an adaptive
   chosen ciphertext attack such as [4] would be useful.

   Both the encryption and the decryption operations of RSAES-OAEP take
   the value of the parameter string P as input. In this version of PKCS
   #1, P is an octet string that is specified explicitly. See Section
   11.2.1 for the relevant ASN.1 syntax.

7.1.1 Encryption operation

   RSAES-OAEP-ENCRYPT ((n, e), M, P)

   Input:
   (n, e)    recipient's RSA public key

   M         message to be encrypted, an octet string of length at
             most k-2-2hLen, where k is the length in octets of the
             modulus n and hLen is the length in octets of the hash
             function output for EME-OAEP

   P         encoding parameters, an octet string that may be empty





Kaliski & Staddon            Informational                     [Page 13]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Output:
   C         ciphertext, an octet string of length k; or "message too
             long"

   Assumptions: public key (n, e) is valid

   Steps:

   1. Apply the EME-OAEP encoding operation (Section 9.1.1.2) to the
   message M and the encoding parameters P to produce an encoded message
   EM of length k-1 octets:

   EM = EME-OAEP-ENCODE (M, P, k-1)

   If the encoding operation outputs "message too long," then output
   "message too long" and stop.

   2. Convert the encoded message EM to an integer message
   representative m: m = OS2IP (EM)

   3. Apply the RSAEP encryption primitive (Section 5.1.1) to the public
   key (n, e) and the message representative m to produce an integer
   ciphertext representative c:

   c = RSAEP ((n, e), m)

   4. Convert the ciphertext representative c to a ciphertext C of
   length k octets: C = I2OSP (c, k)

   5. Output the ciphertext C.

7.1.2 Decryption operation

   RSAES-OAEP-DECRYPT (K, C, P)

   Input:
   K          recipient's RSA private key
   C          ciphertext to be decrypted, an octet string of length
              k, where k is the length in octets of the modulus n
   P          encoding parameters, an octet string that may be empty

   Output:
   M          message, an octet string of length at most k-2-2hLen,
              where hLen is the length in octets of the hash
              function output for EME-OAEP; or "decryption error"






Kaliski & Staddon            Informational                     [Page 14]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Steps:

   1. If the length of the ciphertext C is not k octets, output
   "decryption error" and stop.

   2. Convert the ciphertext C to an integer ciphertext representative
   c: c = OS2IP (C).

   3. Apply the RSADP decryption primitive (Section 5.1.2) to the
   private key K and the ciphertext representative c to produce an
   integer message representative m:

   m = RSADP (K, c)

   If RSADP outputs "ciphertext out of range," then output "decryption
   error" and stop.

   4. Convert the message representative m to an encoded message EM of
   length k-1 octets: EM = I2OSP (m, k-1)

   If I2OSP outputs "integer too large," then output "decryption error"
   and stop.

   5. Apply the EME-OAEP decoding operation to the encoded message EM
   and the encoding parameters P to recover a message M:

   M = EME-OAEP-DECODE (EM, P)

   If the decoding operation outputs "decoding error," then output
   "decryption error" and stop.

   6. Output the message M.

   Note. It is important that the error messages output in steps 4 and 5
   be the same, otherwise an adversary may be able to extract useful
   information from the type of error message received. Error message
   information is used to mount a chosen-ciphertext attack on PKCS #1
   v1.5 encrypted messages in [4].

7.2 RSAES-PKCS1-v1_5

   RSAES-PKCS1-v1_5 combines the RSAEP and RSADP primitives with the
   EME-PKCS1-v1_5 encoding method. It is the same as the encryption
   scheme in PKCS #1 v1.5. RSAES-PKCS1-v1_5 can operate on messages of
   length up to k-11 octets, although care should be taken to avoid
   certain attacks on low-exponent RSA due to Coppersmith, et al. when
   long messages are encrypted (see the third bullet in the notes below
   and [7]).



Kaliski & Staddon            Informational                     [Page 15]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   RSAES-PKCS1-v1_5 does not provide "plaintext aware" encryption. In
   particular, it is possible to generate valid ciphertexts without
   knowing the corresponding plaintexts, with a reasonable probability
   of success. This ability can be exploited in a chosen ciphertext
   attack as shown in [4]. Therefore, if RSAES-PKCS1-v1_5 is to be used,
   certain easily implemented countermeasures should be taken to thwart
   the attack found in [4]. The addition of structure to the data to be
   encoded, rigorous checking of PKCS #1 v1.5 conformance and other
   redundancy in decrypted messages, and the consolidation of error
   messages in a client-server protocol based on PKCS #1 v1.5 can all be
   effective countermeasures and don't involve changes to a PKCS #1
   v1.5-based protocol. These and other countermeasures are discussed in
   [5].

   Notes. The following passages describe some security recommendations
   pertaining to the use of RSAES-PKCS1-v1_5. Recommendations from
   version 1.5 of this document are included as well as new
   recommendations motivated by cryptanalytic advances made in the
   intervening years.

   -It is recommended that the pseudorandom octets in EME-PKCS1-v1_5 be
   generated independently for each encryption process, especially if
   the same data is input to more than one encryption process. Hastad's
   results [13] are one motivation for this recommendation.

   -The padding string PS in EME-PKCS1-v1_5 is at least eight octets
   long, which is a security condition for public-key operations that
   prevents an attacker from recovering data by trying all possible
   encryption blocks.

   -The pseudorandom octets can also help thwart an attack due to
   Coppersmith et al. [7] when the size of the message to be encrypted
   is kept small. The attack works on low-exponent RSA when similar
   messages are encrypted with the same public key. More specifically,
   in one flavor of the attack, when two inputs to RSAEP agree on a
   large fraction of bits (8/9) and low-exponent RSA (e = 3) is used to
   encrypt both of them, it may be possible to recover both inputs with
   the attack. Another flavor of the attack is successful in decrypting
   a single ciphertext when a large fraction (2/3) of the input to RSAEP
   is already known. For typical applications, the message to be
   encrypted is short (e.g., a 128-bit symmetric key) so not enough
   information will be known or common between two messages to enable
   the attack.  However, if a long message is encrypted, or if part of a
   message is known, then the attack may be a concern. In any case, the
   RSAEP-OAEP scheme overcomes the attack.






Kaliski & Staddon            Informational                     [Page 16]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


7.2.1 Encryption operation

   RSAES-PKCS1-V1_5-ENCRYPT ((n, e), M)

   Input:
   (n, e)  recipient's RSA public key
   M       message to be encrypted, an octet string of length at
           most k-11 octets, where k is the length in octets of the
           modulus n

   Output:
   C       ciphertext, an octet string of length k; or "message too
           long"

   Steps:

   1. Apply the EME-PKCS1-v1_5 encoding operation (Section 9.1.2.1) to
   the message M to produce an encoded message EM of length k-1 octets:

   EM = EME-PKCS1-V1_5-ENCODE (M, k-1)

   If the encoding operation outputs "message too long," then output
   "message too long" and stop.

   2. Convert the encoded message EM to an integer message
   representative m: m = OS2IP (EM)

   3. Apply the RSAEP encryption primitive (Section 5.1.1) to the public
   key (n, e) and the message representative m to produce an integer
   ciphertext representative c: c = RSAEP ((n, e), m)

   4. Convert the ciphertext representative c to a ciphertext C of
   length k octets: C = I2OSP (c, k)

   5. Output the ciphertext C.

7.2.2 Decryption operation

   RSAES-PKCS1-V1_5-DECRYPT (K, C)

   Input:
   K       recipient's RSA private key
   C       ciphertext to be decrypted, an octet string of length k,
           where k is the length in octets of the modulus n

   Output:
   M       message, an octet string of length at most k-11; or
           "decryption error"



Kaliski & Staddon            Informational                     [Page 17]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Steps:

   1. If the length of the ciphertext C is not k octets, output
   "decryption error" and stop.

   2. Convert the ciphertext C to an integer ciphertext representative
   c: c = OS2IP (C).

   3. Apply the RSADP decryption primitive to the private key (n, d) and
   the ciphertext representative c to produce an integer message
   representative m: m = RSADP ((n, d), c).

   If RSADP outputs "ciphertext out of range," then output "decryption
   error" and stop.

   4. Convert the message representative m to an encoded message EM of
   length k-1 octets: EM = I2OSP (m, k-1)

   If I2OSP outputs "integer too large," then output "decryption error"
   and stop.

   5. Apply the EME-PKCS1-v1_5 decoding operation to the encoded message
   EM to recover a message M: M = EME-PKCS1-V1_5-DECODE (EM).

   If the decoding operation outputs "decoding error," then output
   "decryption error" and stop.

   6. Output the message M.

   Note. It is important that only one type of error message is output
   by EME-PKCS1-v1_5, as ensured by steps 4 and 5. If this is not done,
   then an adversary may be able to use information extracted form the
   type of error message received to mount a chosen-ciphertext attack
   such as the one found in [4].

8. Signature schemes with appendix

   A signature scheme with appendix consists of a signature generation
   operation and a signature verification operation, where the signature
   generation operation produces a signature from a message with a
   signer's private key, and the signature verification operation
   verifies the signature on the message with the signer's corresponding
   public key.  To verify a signature constructed with this type of
   scheme it is necessary to have the message itself. In this way,
   signature schemes with appendix are distinguished from signature
   schemes with message recovery, which are not supported in this
   document.




Kaliski & Staddon            Informational                     [Page 18]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   A signature scheme with appendix can be employed in a variety of
   applications. For instance, X.509 [6] employs such a scheme to
   authenticate the content of a certificate; the signature scheme with
   appendix defined here would be a suitable signature algorithm in that
   context. A related signature scheme could be employed in PKCS #7
   [21], although for technical reasons, the current version of PKCS #7
   separates a hash function from a signature scheme, which is different
   than what is done here.

   One signature scheme with appendix is specified in this document:
   RSASSA-PKCS1-v1_5.

   The signature scheme with appendix given here follows a general model
   similar to that employed in IEEE P1363, by combining signature and
   verification primitives with an encoding method for signatures. The
   signature generation operations apply a message encoding operation to
   a message to produce an encoded message, which is then converted to
   an integer message representative. A signature primitive is then
   applied to the message representative to produce the signature. The
   signature verification operations apply a signature verification
   primitive to the signature to recover a message representative, which
   is then converted to an octet string. The message encoding operation
   is again applied to the message, and the result is compared to the
   recovered octet string. If there is a match, the signature is
   considered valid. (Note that this approach assumes that the signature
   and verification primitives have the message-recovery form and the
   encoding method is deterministic, as is the case for RSASP1/RSAVP1
   and EMSA-PKCS1-v1_5. The signature generation and verification
   operations have a different form in P1363 for other primitives and
   encoding methods.)

   Editor's note. RSA Laboratories is investigating the possibility of
   including a scheme based on the PSS encoding methods specified in
   [3], which would be recommended for new applications.

8.1 RSASSA-PKCS1-v1_5

   RSASSA-PKCS1-v1_5 combines the RSASP1 and RSAVP1 primitives with the
   EME-PKCS1-v1_5 encoding method. It is compatible with the IFSSA
   scheme defined in the draft P1363 where the signature and
   verification primitives are IFSP-RSA1 and IFVP-RSA1 and the message
   encoding method is EMSA-PKCS1-v1_5 (which is not defined in P1363).
   The length of messages on which RSASSA-PKCS1-v1_5 can operate is
   either unrestricted or constrained by a very large number, depending
   on the hash function underlying the message encoding method.






Kaliski & Staddon            Informational                     [Page 19]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Assuming that the hash function in EMSA-PKCS1-v1_5 has appropriate
   properties and the key size is sufficiently large, RSASSA-PKCS1-v1_5
   provides secure signatures, meaning that it is computationally
   infeasible to generate a signature without knowing the private key,
   and computationally infeasible to find a message with a given
   signature or two messages with the same signature. Also, in the
   encoding method EMSA-PKCS1-v1_5, a hash function identifier is
   embedded in the encoding.  Because of this feature, an adversary must
   invert or find collisions of the particular hash function being used;
   attacking a different hash function than the one selected by the
   signer is not useful to the adversary.

8.1.1 Signature generation operation

   RSASSA-PKCS1-V1_5-SIGN (K, M)
   Input:
   K         signer's RSA private ke
   M         message to be signed, an octet string

   Output:
   S         signature, an octet string of length k, where k is the
             length in octets of the modulus n; "message too long" or
             "modulus too short"
   Steps:

   1. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to
   the message M to produce an encoded message EM of length k-1 octets:

   EM = EMSA-PKCS1-V1_5-ENCODE (M, k-1)

   If the encoding operation outputs "message too long," then output
   "message too long" and stop. If the encoding operation outputs
   "intended encoded message length too short" then output "modulus too
   short".

   2. Convert the encoded message EM to an integer message
   representative m: m = OS2IP (EM)

   3. Apply the RSASP1 signature primitive (Section 5.2.1) to the
   private key K and the message representative m to produce an integer
   signature representative s: s = RSASP1 (K, m)

   4. Convert the signature representative s to a signature S of length
   k octets: S = I2OSP (s, k)

   5. Output the signature S.





Kaliski & Staddon            Informational                     [Page 20]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


8.1.2 Signature verification operation

   RSASSA-PKCS1-V1_5-VERIFY ((n, e), M, S)

   Input:
   (n, e)    signer's RSA public key
   M         message whose signature is to be verified, an octet string
   S         signature to be verified, an octet string of length k,
             where k is the length in octets of the modulus n

   Output: "valid signature," "invalid signature," or "message too
   long", or "modulus too short"

   Steps:

   1. If the length of the signature S is not k octets, output "invalid
   signature" and stop.

   2. Convert the signature S to an integer signature representative s:

   s = OS2IP (S)

   3. Apply the RSAVP1 verification primitive (Section 5.2.2) to the
   public key (n, e) and the signature representative s to produce an
   integer message representative m:

   m = RSAVP1 ((n, e), s)                  If RSAVP1 outputs "invalid"
   then output "invalid signature" and stop.

   4. Convert the message representative m to an encoded message EM of
   length k-1 octets: EM = I2OSP (m, k-1)

   If I2OSP outputs "integer too large," then output "invalid signature"
   and stop.

   5. Apply the EMSA-PKCS1-v1_5 encoding operation (Section 9.2.1) to
   the message M to produce a second encoded message EM' of length k-1
   octets:

   EM' = EMSA-PKCS1-V1_5-ENCODE (M, k-1)

   If the encoding operation outputs "message too long," then output
   "message too long" and stop. If the encoding operation outputs
   "intended encoded message length too short" then output "modulus too
   short".






Kaliski & Staddon            Informational                     [Page 21]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   6. Compare the encoded message EM and the second encoded message EM'.
   If they are the same, output "valid signature"; otherwise, output
   "invalid signature."

9. Encoding methods

   Encoding methods consist of operations that map between octet string
   messages and integer message representatives.

   Two types of encoding method are considered in this document:
   encoding methods for encryption, encoding methods for signatures with
   appendix.

9.1 Encoding methods for encryption

   An encoding method for encryption consists of an encoding operation
   and a decoding operation. An encoding operation maps a message M to a
   message representative EM of a specified length; the decoding
   operation maps a message representative EM back to a message. The
   encoding and decoding operations are inverses.

   The message representative EM will typically have some structure that
   can be verified by the decoding operation; the decoding operation
   will output "decoding error" if the structure is not present. The
   encoding operation may also introduce some randomness, so that
   different applications of the encoding operation to the same message
   will produce different representatives.

   Two encoding methods for encryption are employed in the encryption
   schemes and are specified here: EME-OAEP and EME-PKCS1-v1_5.

9.1.1 EME-OAEP

   This encoding method is parameterized by the choice of hash function
   and mask generation function. Suggested hash and mask generation
   functions are given in Section 10. This encoding method is based on
   the method found in [2].

9.1.1.1 Encoding operation

   EME-OAEP-ENCODE (M, P, emLen)

   Options:
   Hash      hash function (hLen denotes the length in octet of the
             hash function output)
   MGF       mask generation function





Kaliski & Staddon            Informational                     [Page 22]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Input:
   M         message to be encoded, an octet string of length at most
             emLen-1-2hLen
   P         encoding parameters, an octet string
   emLen     intended length in octets of the encoded message, at least
             2hLen+1

   Output:
   EM        encoded message, an octet string of length emLen;
             "message too long" or "parameter string too long"

   Steps:

   1. If the length of P is greater than the input limitation for the
   hash function (2^61-1 octets for SHA-1) then output "parameter string
   too long" and stop.

   2. If ||M|| > emLen-2hLen-1 then output "message too long" and stop.

   3. Generate an octet string PS consisting of emLen-||M||-2hLen-1 zero
   octets. The length of PS may be 0.

   4. Let pHash = Hash(P), an octet string of length hLen.

   5. Concatenate pHash, PS, the message M, and other padding to form a
   data block DB as: DB = pHash || PS || 01 || M

   6. Generate a random octet string seed of length hLen.

   7. Let dbMask = MGF(seed, emLen-hLen).

   8. Let maskedDB = DB \xor dbMask.

   9. Let seedMask = MGF(maskedDB, hLen).

   10. Let maskedSeed = seed \xor seedMask.

   11. Let EM = maskedSeed || maskedDB.

   12. Output EM.

9.1.1.2 Decoding operation EME-OAEP-DECODE (EM, P)

   Options:
   Hash      hash function (hLen denotes the length in octet of the hash
             function output)

   MGF       mask generation function



Kaliski & Staddon            Informational                     [Page 23]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Input:

   EM        encoded message, an octet string of length at least 2hLen+1
   P         encoding parameters, an octet string

   Output:
   M         recovered message, an octet string of length at most
             ||EM||-1-2hLen; or "decoding error"

   Steps:

   1. If the length of P is greater than the input limitation for the
   hash function (2^61-1 octets for SHA-1) then output "parameter string
   too long" and stop.

   2. If ||EM|| < 2hLen+1, then output "decoding error" and stop.

   3. Let maskedSeed be the first hLen octets of EM and let maskedDB be
   the remaining ||EM|| - hLen octets.

   4. Let seedMask = MGF(maskedDB, hLen).

   5. Let seed = maskedSeed \xor seedMask.

   6. Let dbMask = MGF(seed, ||EM|| - hLen).

   7. Let DB = maskedDB \xor dbMask.

   8. Let pHash = Hash(P), an octet string of length hLen.

   9. Separate DB into an octet string pHash' consisting of the first
   hLen octets of DB, a (possibly empty) octet string PS consisting of
   consecutive zero octets following pHash', and a message M as:

   DB = pHash' || PS || 01 || M

   If there is no 01 octet to separate PS from M, output "decoding
   error" and stop.

   10. If pHash' does not equal pHash, output "decoding error" and stop.

   11. Output M.

9.1.2 EME-PKCS1-v1_5

   This encoding method is the same as in PKCS #1 v1.5, Section 8:
   Encryption Process.




Kaliski & Staddon            Informational                     [Page 24]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


9.1.2.1 Encoding operation

   EME-PKCS1-V1_5-ENCODE (M, emLen)

   Input:
   M         message to be encoded, an octet string of length at most
             emLen-10
   emLen     intended length in octets of the encoded message

   Output:
   EM        encoded message, an octet string of length emLen; or
             "message too long"

   Steps:

   1. If the length of the message M is greater than emLen - 10 octets,
   output "message too long" and stop.

   2. Generate an octet string PS of length emLen-||M||-2 consisting of
   pseudorandomly generated nonzero octets. The length of PS will be at
   least 8 octets.

   3. Concatenate PS, the message M, and other padding to form the
   encoded message EM as:

   EM = 02 || PS || 00 || M

   4. Output EM.

9.1.2.2 Decoding operation

   EME-PKCS1-V1_5-DECODE (EM)

   Input:
   EM      encoded message, an octet string of length at least 10

   Output:
   M       recovered message, an octet string of length at most
           ||EM||-10; or "decoding error"

   Steps:

   1. If the length of the encoded message EM is less than 10, output
   "decoding error" and stop.

   2. Separate the encoded message EM into an octet string PS consisting
   of nonzero octets and a message M as: EM = 02 || PS || 00 || M.




Kaliski & Staddon            Informational                     [Page 25]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   If the first octet of EM is not 02, or if there is no 00 octet to
   separate PS from M, output "decoding error" and stop.

   3. If the length of PS is less than 8 octets, output "decoding error"
   and stop.

   4. Output M.

9.2 Encoding methods for signatures with appendix

   An encoding method for signatures with appendix, for the purposes of
   this document, consists of an encoding operation. An encoding
   operation maps a message M to a message representative EM of a
   specified length. (In future versions of this document, encoding
   methods may be added that also include a decoding operation.)

   One encoding method for signatures with appendix is employed in the
   encryption schemes and is specified here: EMSA-PKCS1-v1_5.

9.2.1 EMSA-PKCS1-v1_5

   This encoding method only has an encoding operation.

   EMSA-PKCS1-v1_5-ENCODE (M, emLen)

   Option:
   Hash      hash function (hLen denotes the length in octet of the hash
             function output)

   Input:
   M         message to be encoded
   emLen     intended length in octets of the encoded message, at least
             ||T|| + 10, where T is the DER encoding of a certain value
             computed during the encoding operation

   Output:
   EM        encoded message, an octet string of length emLen; or "message
             too long" or "intended encoded message length too short"

   Steps:

   1. Apply the hash function to the message M to produce a hash value
   H:

   H = Hash(M).

   If the hash function outputs "message too long," then output "message
   too long".



Kaliski & Staddon            Informational                     [Page 26]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   2. Encode the algorithm ID for the hash function and the hash value
   into an ASN.1 value of type DigestInfo (see Section 11) with the
   Distinguished Encoding Rules (DER), where the type DigestInfo has the
   syntax

   DigestInfo::=SEQUENCE{
     digestAlgorithm  AlgorithmIdentifier,
     digest OCTET STRING }

   The first field identifies the hash function and the second contains
   the hash value. Let T be the DER encoding.

   3. If emLen is less than ||T|| + 10 then output "intended encoded
   message length too short".

   4. Generate an octet string PS consisting of emLen-||T||-2 octets
   with value FF (hexadecimal). The length of PS will be at least 8
   octets.

   5. Concatenate PS, the DER encoding T, and other padding to form the
   encoded message EM as: EM = 01 || PS || 00 || T

   6. Output EM.

10. Auxiliary Functions

   This section specifies the hash functions and the mask generation
   functions that are mentioned in the encoding methods (Section 9).

10.1 Hash Functions

   Hash functions are used in the operations contained in Sections 7, 8
   and 9. Hash functions are deterministic, meaning that the output is
   completely determined by the input. Hash functions take octet strings
   of variable length, and generate fixed length octet strings. The hash
   functions used in the operations contained in Sections 7, 8 and 9
   should be collision resistant. This means that it is infeasible to
   find two distinct inputs to the hash function that produce the same
   output. A collision resistant hash function also has the desirable
   property of being one-way; this means that given an output, it is
   infeasible to find an input whose hash is the specified output. The
   property of collision resistance is especially desirable for RSASSA-
   PKCS1-v1_5, as it makes it infeasible to forge signatures. In
   addition to the requirements, the hash function should yield a mask
   generation function  (Section 10.2) with pseudorandom output.






Kaliski & Staddon            Informational                     [Page 27]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Three hash functions are recommended for the encoding methods in this
   document: MD2 [15], MD5 [17], and SHA-1 [16]. For the EME-OAEP
   encoding method, only SHA-1 is recommended. For the EMSA-PKCS1-v1_5
   encoding method, SHA-1 is recommended for new applications. MD2 and
   MD5 are recommended only for compatibility with existing applications
   based on PKCS #1 v1.5.

   The hash functions themselves are not defined here; readers are
   referred to the appropriate references ([15], [17] and [16]).

   Note. Version 1.5 of this document also allowed for the use of MD4 in
   signature schemes. The cryptanalysis of MD4 has progressed
   significantly in the intervening years. For example, Dobbertin [10]
   demonstrated how to find collisions for MD4 and that the first two
   rounds of MD4 are not one-way [11]. Because of these results and
   others (e.g. [9]), MD4 is no longer recommended. There have also been
   advances in the cryptanalysis of MD2 and MD5, although not enough to
   warrant removal from existing applications. Rogier and Chauvaud [19]
   demonstrated how to find collisions in a modified version of MD2. No
   one has demonstrated how to find collisions for the full MD5
   algorithm, although partial results have been found (e.g. [8]). For
   new applications, to address these concerns, SHA-1 is preferred.

10.2 Mask Generation Functions

   A mask generation function takes an octet string of variable length
   and a desired output length as input, and outputs an octet string of
   the desired length. There may be restrictions on the length of the
   input and output octet strings, but such bounds are generally very
   large. Mask generation functions are deterministic; the octet string
   output is completely determined by the input octet string. The output
   of a mask generation function should be pseudorandom, that is, if the
   seed to the function is unknown, it should be infeasible to
   distinguish the output from a truly random string. The plaintext-
   awareness of RSAES-OAEP relies on the random nature of the output of
   the mask generation function, which in turn relies on the random
   nature of the underlying hash.

   One mask generation function is recommended for the encoding methods
   in this document, and is defined here: MGF1, which is based on a hash
   function. Future versions of this document may define other mask
   generation functions.

10.2.1 MGF1

   MGF1 is a Mask Generation Function based on a hash function.

   MGF1 (Z, l)



Kaliski & Staddon            Informational                     [Page 28]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   Options:
   Hash    hash function (hLen denotes the length in octets of the hash
           function output)

   Input:
   Z       seed from which mask is generated, an octet string
   l       intended length in octets of the mask, at most 2^32(hLen)

   Output:
   mask    mask, an octet string of length l; or "mask too long"

   Steps:

   1.If l > 2^32(hLen), output "mask too long" and stop.

   2.Let T  be the empty octet string.

   3.For counter from 0 to \lceil{l / hLen}\rceil-1, do the following:

   a.Convert counter to an octet string C of length 4 with the primitive
   I2OSP: C = I2OSP (counter, 4)

   b.Concatenate the hash of the seed Z and C to the octet string T: T =
   T || Hash (Z || C)

   4.Output the leading l octets of T as the octet string mask.

11. ASN.1 syntax

11.1 Key representation

   This section defines ASN.1 object identifiers for RSA public and
   private keys, and defines the types RSAPublicKey and RSAPrivateKey.
   The intended application of these definitions includes X.509
   certificates, PKCS #8 [22], and PKCS #12 [23].

   The object identifier rsaEncryption identifies RSA public and private
   keys as defined in Sections 11.1.1 and 11.1.2. The parameters field
   associated with this OID in an AlgorithmIdentifier shall have type
   NULL.

   rsaEncryption OBJECT IDENTIFIER ::= {pkcs-1 1}

   All of the definitions in this section are the same as in PKCS #1
   v1.5.






Kaliski & Staddon            Informational                     [Page 29]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


11.1.1 Public-key syntax

   An RSA public key should be represented with the ASN.1 type
   RSAPublicKey:

   RSAPublicKey::=SEQUENCE{
     modulus INTEGER, -- n
     publicExponent INTEGER -- e }

   (This type is specified in X.509 and is retained here for
   compatibility.)

   The fields of type RSAPublicKey have the following meanings:
   -modulus is the modulus n.
   -publicExponent is the public exponent e.

11.1.2 Private-key syntax

   An RSA private key should be represented with ASN.1 type
   RSAPrivateKey:

   RSAPrivateKey ::= SEQUENCE {
     version Version,
     modulus INTEGER, -- n
     publicExponent INTEGER, -- e
     privateExponent INTEGER, -- d
     prime1 INTEGER, -- p
     prime2 INTEGER, -- q
     exponent1 INTEGER, -- d mod (p-1)
     exponent2 INTEGER, -- d mod (q-1)
     coefficient INTEGER -- (inverse of q) mod p }

   Version ::= INTEGER

   The fields of type RSAPrivateKey have the following meanings:

   -version is the version number, for compatibility with future
   revisions of this document. It shall be 0 for this version of the
   document.
   -modulus is the modulus n.
   -publicExponent is the public exponent e.
   -privateExponent is the private exponent d.
   -prime1 is the prime factor p of n.
   -prime2 is the prime factor q of n.
   -exponent1 is d mod (p-1).
   -exponent2 is d mod (q-1).
   -coefficient is the Chinese Remainder Theorem coefficient q-1 mod p.




Kaliski & Staddon            Informational                     [Page 30]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


11.2 Scheme identification

   This section defines object identifiers for the encryption and
   signature schemes. The schemes compatible with PKCS #1 v1.5 have the
   same definitions as in PKCS #1 v1.5. The intended application of
   these definitions includes X.509 certificates and PKCS #7.

11.2.1 Syntax for RSAES-OAEP

   The object identifier id-RSAES-OAEP identifies the RSAES-OAEP
   encryption scheme.

   id-RSAES-OAEP OBJECT IDENTIFIER ::= {pkcs-1 7}

   The parameters field associated with this OID in an
   AlgorithmIdentifier shall have type RSAEP-OAEP-params:

   RSAES-OAEP-params ::=  SEQUENCE {
     hashFunc [0] AlgorithmIdentifier {{oaepDigestAlgorithms}}
       DEFAULT sha1Identifier,
     maskGenFunc [1] AlgorithmIdentifier {{pkcs1MGFAlgorithms}}
       DEFAULT mgf1SHA1Identifier,
     pSourceFunc [2] AlgorithmIdentifier
       {{pkcs1pSourceAlgorithms}}
       DEFAULT pSpecifiedEmptyIdentifier }

   The fields of type RSAES-OAEP-params have the following meanings:

   -hashFunc identifies the hash function. It shall be an algorithm ID
   with an OID in the set oaepDigestAlgorithms, which for this version
   shall consist of id-sha1, identifying the SHA-1 hash function. The
   parameters field for id-sha1 shall have type NULL.

   oaepDigestAlgorithms ALGORITHM-IDENTIFIER ::= {
     {NULL IDENTIFIED BY id-sha1} }

   id-sha1 OBJECT IDENTIFIER ::=
     {iso(1) identified-organization(3) oiw(14) secsig(3)
       algorithms(2) 26}


   The default hash function is SHA-1:
   sha1Identifier ::= AlgorithmIdentifier {id-sha1, NULL}

   -maskGenFunc identifies the mask generation function. It shall be an
   algorithm ID with an OID in the set pkcs1MGFAlgorithms, which for
   this version shall consist of id-mgf1, identifying the MGF1 mask
   generation function (see Section 10.2.1). The parameters field for



Kaliski & Staddon            Informational                     [Page 31]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   id-mgf1 shall have type AlgorithmIdentifier, identifying the hash
   function on which MGF1 is based, where the OID for the hash function
   shall be in the set oaepDigestAlgorithms.

   pkcs1MGFAlgorithms ALGORITHM-IDENTIFIER ::= {
     {AlgorithmIdentifier {{oaepDigestAlgorithms}} IDENTIFIED
       BY id-mgf1} }

   id-mgf1 OBJECT IDENTIFIER ::= {pkcs-1 8}

   The default mask generation function is MGF1 with SHA-1:

   mgf1SHA1Identifier ::= AlgorithmIdentifier {
     id-mgf1, sha1Identifier }

   -pSourceFunc identifies the source (and possibly the value) of the
   encoding parameters P. It shall be an algorithm ID with an OID in the
   set pkcs1pSourceAlgorithms, which for this version shall consist of
   id-pSpecified, indicating that the encoding parameters are specified
   explicitly. The parameters field for id-pSpecified shall have type
   OCTET STRING, containing the encoding parameters.

   pkcs1pSourceAlgorithms ALGORITHM-IDENTIFIER ::= {
     {OCTET STRING IDENTIFIED BY id-pSpecified} }

   id-pSpecified OBJECT IDENTIFIER ::= {pkcs-1 9}

   The default encoding parameters is an empty string (so that pHash in
   EME-OAEP will contain the hash of the empty string):

   pSpecifiedEmptyIdentifier ::= AlgorithmIdentifier {
     id-pSpecified, OCTET STRING SIZE (0) }

   If all of the default values of the fields in RSAES-OAEP-params are
   used, then the algorithm identifier will have the following value:

   RSAES-OAEP-Default-Identifier ::= AlgorithmIdentifier {
     id-RSAES-OAEP,
     {sha1Identifier,
      mgf1SHA1Identifier,
      pSpecifiedEmptyIdentifier } }

11.2.2 Syntax for RSAES-PKCS1-v1_5

   The object identifier rsaEncryption (Section 11.1) identifies the
   RSAES-PKCS1-v1_5 encryption scheme. The parameters field associated
   with this OID in an AlgorithmIdentifier shall have type NULL. This is
   the same as in PKCS #1 v1.5.



Kaliski & Staddon            Informational                     [Page 32]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   RsaEncryption   OBJECT IDENTIFIER ::= {PKCS-1 1}

11.2.3 Syntax for RSASSA-PKCS1-v1_5

   The object identifier for RSASSA-PKCS1-v1_5 shall be one of the
   following. The choice of OID depends on the choice of hash algorithm:
   MD2, MD5 or SHA-1. Note that if either MD2 or MD5 is used then the
   OID is just as in PKCS #1 v1.5. For each OID, the parameters field
   associated with this OID in an AlgorithmIdentifier shall have type
   NULL.

   If the hash function to be used is MD2, then the OID should be:

   md2WithRSAEncryption ::= {PKCS-1 2}

   If the hash function to be used is MD5, then the OID should be:

   md5WithRSAEncryption ::= {PKCS-1 4}

   If the hash function to be used is SHA-1, then the OID should be:

   sha1WithRSAEncryption ::= {pkcs-1 5}

   In the digestInfo type mentioned in Section 9.2.1 the OIDS for the
   digest algorithm are the following:

   id-SHA1 OBJECT IDENTIFIER ::=
           {iso(1) identified-organization(3) oiw(14) secsig(3)
            algorithms(2) 26 }

   md2 OBJECT IDENTIFIER ::=
           {iso(1) member-body(2) US(840) rsadsi(113549)
            digestAlgorithm(2) 2}

   md5 OBJECT IDENTIFIER ::=
           {iso(1) member-body(2) US(840) rsadsi(113549)
            digestAlgorithm(2) 5}

   The parameters field of the digest algorithm has ASN.1 type NULL for
   these OIDs.

12. Patent statement

   The Internet Standards Process as defined in RFC 1310 requires a
   written statement from the Patent holder that a license will be made
   available to applicants under reasonable terms and conditions prior
   to approving a specification as a Proposed, Draft or Internet
   Standard.



Kaliski & Staddon            Informational                     [Page 33]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   The Internet Society, Internet Architecture Board, Internet
   Engineering Steering Group and the Corporation for National Research
   Initiatives take no position on the validity or scope of the
   following patents and patent applications, nor on the appropriateness
   of the terms of the assurance. The Internet Society and other groups
   mentioned above have not made any determination as to any other
   intellectual property rights which may apply to the practice of this
   standard.  Any further consideration of these matters is the user's
   responsibility.

12.1 Patent statement for the RSA algorithm

   The Massachusetts Institute of Technology has granted RSA Data
   Security, Inc., exclusive sub-licensing rights to the following
   patent issued in the United States:

   Cryptographic Communications System and Method ("RSA"), No. 4,405,829

   RSA Data Security, Inc. has provided the following statement with
   regard to this patent:

   It is RSA's business practice to make licenses to its patents
   available on reasonable and nondiscriminatory terms. Accordingly, RSA
   is willing, upon request, to grant non-exclusive licenses to such
   patent on reasonable and non-discriminatory terms and conditions to
   those who respect RSA's intellectual property rights and subject to
   RSA's then current royalty rate for the patent licensed. The royalty
   rate for the RSA patent is presently set at 2% of the licensee's
   selling price for each product covered by the patent.  Any requests
   for license information may be directed to:

            Director of Licensing
            RSA Data Security, Inc.
            2955 Campus Drive
            Suite 400
            San Mateo, CA 94403

   A license under RSA's patent(s) does not include any rights to know-
   how or other technical information or license under other
   intellectual property rights.  Such license does not extend to any
   activities which constitute infringement or inducement thereto. A
   licensee must make his own determination as to whether a license is
   necessary under patents of others.








Kaliski & Staddon            Informational                     [Page 34]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


13. Revision history

   Versions 1.0-1.3

   Versions 1.0-1.3 were distributed to participants in RSA Data
   Security, Inc.'s Public-Key Cryptography Standards meetings in
   February and March 1991.


   Version 1.4

   Version 1.4 was part of the June 3, 1991 initial public release of
   PKCS. Version 1.4 was published as NIST/OSI Implementors' Workshop
   document SEC-SIG-91-18.


   Version 1.5

   Version 1.5 incorporates several editorial changes, including updates
   to the references and the addition of a revision history. The
   following substantive changes were made: -Section 10: "MD4 with RSA"
   signature and verification processes were added.

   -Section 11: md4WithRSAEncryption object identifier was added.

   Version 2.0 [DRAFT]

   Version 2.0 incorporates major editorial changes in terms of the
   document structure, and introduces the RSAEP-OAEP encryption scheme.
   This version continues to support the encryption and signature
   processes in version 1.5, although the hash algorithm MD4 is no
   longer allowed due to cryptanalytic advances in the intervening
   years.

14. References

   [1] ANSI, ANSI X9.44: Key Management Using Reversible Public Key
       Cryptography for the Financial Services Industry. Work in
       Progress.

   [2] M. Bellare and P. Rogaway. Optimal Asymmetric Encryption - How to
       Encrypt with RSA. In Advances in Cryptology-Eurocrypt '94, pp.
       92-111, Springer-Verlag, 1994.

   [3] M. Bellare and P. Rogaway. The Exact Security of Digital
       Signatures - How to Sign with RSA and Rabin. In Advances in
       Cryptology-Eurocrypt '96, pp. 399-416, Springer-Verlag, 1996.




Kaliski & Staddon            Informational                     [Page 35]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   [4] D. Bleichenbacher. Chosen Ciphertext Attacks against Protocols
       Based on the RSA Encryption Standard PKCS #1. To appear in
       Advances in Cryptology-Crypto '98.

   [5] D. Bleichenbacher, B. Kaliski and J. Staddon. Recent Results on
       PKCS #1: RSA Encryption Standard. RSA Laboratories' Bulletin,
       Number 7, June 24, 1998.

   [6] CCITT. Recommendation X.509: The Directory-Authentication
       Framework. 1988.

   [7] D. Coppersmith, M. Franklin, J. Patarin and M. Reiter. Low-
       Exponent RSA with Related Messages. In Advances in Cryptology-
       Eurocrypt '96, pp. 1-9, Springer-Verlag, 1996

   [8] B. Den Boer and Bosselaers. Collisions for the Compression
       Function of MD5. In Advances in Cryptology-Eurocrypt '93, pp
       293-304, Springer-Verlag, 1994.

   [9] B. den Boer, and A. Bosselaers. An Attack on the Last Two Rounds
       of MD4. In Advances in Cryptology-Crypto '91, pp.194-203,
       Springer-Verlag, 1992.

   [10] H. Dobbertin. Cryptanalysis of MD4. Fast Software Encryption.
        Lecture Notes in Computer Science, Springer-Verlag 1996, pp.
        55-72.

   [11] H. Dobbertin. Cryptanalysis of MD5 Compress. Presented at the
        rump session of Eurocrypt `96, May 14, 1996

   [12] H. Dobbertin.The First Two Rounds of MD4 are Not One-Way. Fast
        Software Encryption. Lecture Notes in Computer Science,
        Springer-Verlag 1998, pp. 284-292.

   [13] J. Hastad. Solving Simultaneous Modular Equations of Low Degree.
        SIAM Journal of Computing, 17, 1988, pp. 336-341.

   [14] IEEE. IEEE P1363: Standard Specifications for Public Key
        Cryptography. Draft Version 4.

   [15] Kaliski, B., "The MD2 Message-Digest Algorithm", RFC 1319, April
        1992.

   [16] National Institute of Standards and Technology (NIST). FIPS
        Publication 180-1: Secure Hash Standard. April 1994.

   [17] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April
        1992.



Kaliski & Staddon            Informational                     [Page 36]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


   [18] R. Rivest, A. Shamir and L. Adleman. A Method for Obtaining
        Digital Signatures and Public-Key Cryptosystems. Communications
        of the ACM, 21(2), pp. 120-126, February 1978.

   [19] N. Rogier and P. Chauvaud. The Compression Function of MD2 is
        not Collision Free. Presented at Selected Areas of Cryptography
        `95. Carleton University, Ottawa, Canada. May 18-19, 1995.

   [20] RSA Laboratories. PKCS #1: RSA Encryption Standard. Version 1.5,
        November 1993.

   [21] RSA Laboratories. PKCS #7: Cryptographic Message Syntax
        Standard. Version 1.5, November 1993.

   [22] RSA  Laboratories. PKCS #8: Private-Key Information Syntax
        Standard. Version 1.2, November 1993.

   [23] RSA Laboratories. PKCS #12: Personal Information Exchange Syntax
        Standard. Version 1.0, Work in Progress, April 1997.

Security Considerations

   Security issues are discussed throughout this memo.

Acknowledgements

   This document is based on a contribution of RSA Laboratories, a
   division of RSA Data Security, Inc.  Any substantial use of the text
   from this document must acknowledge RSA Data Security, Inc. RSA Data
   Security, Inc. requests that all material mentioning or referencing
   this document identify this as "RSA Data Security, Inc. PKCS #1
   v2.0".



















Kaliski & Staddon            Informational                     [Page 37]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


Authors' Addresses

   Burt Kaliski
   RSA Laboratories East
   20 Crosby Drive
   Bedford, MA  01730

   Phone: (617) 687-7000
   EMail: burt@rsa.com


   Jessica Staddon
   RSA Laboratories West
   2955 Campus Drive
   Suite 400
   San Mateo, CA 94403

   Phone: (650) 295-7600
   EMail: jstaddon@rsa.com
































Kaliski & Staddon            Informational                     [Page 38]

RFC 2437        PKCS #1: RSA Cryptography Specifications    October 1998


Full Copyright Statement

   Copyright (C) The Internet Society (1998).  All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works.  However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assigns.

   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
























Kaliski & Staddon            Informational                     [Page 39]