📄 rsa src.txt
字号:
发信人: iceman ( 令狐小冲), 信区: Security
标 题: RSA src
发信站: 武汉白云黄鹤站 (Fri Sep 4 11:25:50 1998) , 站内信件
From xs4all!mail2news Fri Dec 29 09:31:08 1995
Path: xs4all!mail2news
From: cpunk@remail.ecafe.org (ECafe Anonymous Remailer)
Newsgroups: list.cypherpunks
Subject: Cryptolib 1.1 rsa.c
Date: 28 Dec 95 17:22:57 GMT
Organization: XS4ALL, networking for the masses
Lines: 651
Sender: owner-cypherpunks@toad.com
Message-ID: <199512281722.RAA18284@pangaea.ang.ecafe.org>
NNTP-Posting-Host: xs1.xs4all.nl
I am informed that there is a serious bug in the version of cryptolib
that gets sent to people who don't have RSA licenses. The bug
prevents it from doing RSA encrypt, decrypt or signature. I cannot
imagine how this bug slipped through but it seems only to exist in the
copies of cryptolib that are sent to those without RSA licenses.
Fortunately I have an RSA licesnse and so my new copy (thanks Jack and
Matt!) does not suffer from the bug.
Here is the version of rsa.c that fixes the bug.
/*
* This is version 1.1 of CryptoLib
*
* The authors of this software are Jack Lacy, Don Mitchell and Matt Blaze
* Copyright (c) 1991, 1992, 1993, 1994, 1995 by AT&T.
* Permission to use, copy, and modify this software without fee
* is hereby granted, provided that this entire notice is included in
* all copies of any software which is or includes a copy or
* modification of this software and in all copies of the supporting
* documentation for such software.
*
* NOTE:
* Some of the algorithms in cryptolib may be covered by patents.
* It is the responsibility of the user to ensure that any required
* licenses are obtained.
*
*
* SOME PARTS OF CRYPTOLIB MAY BE RESTRICTED UNDER UNITED STATES EXPORT
* REGULATIONS.
*
*
* THIS SOFTWARE IS BEING PROVIDED "AS IS", WITHOUT ANY EXPRESS OR IMPLIED
* WARRANTY. IN PARTICULAR, NEITHER THE AUTHORS NOR AT&T MAKE ANY
* REPRESENTATION OR WARRANTY OF ANY KIND CONCERNING THE MERCHANTABILITY
* OF THIS SOFTWARE OR ITS FITNESS FOR ANY PARTICULAR PURPOSE.
*/
/*
* Code for generating and manipulating RSA keys
* and doing encryption and decryption using RSA.
* AT&T recognizes that RSA is patented
* (Rivest et. al. U.S. Patent 4,405,829, issued 9/20/83).
* Use of this code assumes proper licensing.
*
* coded by Jack Lacy, December, 1991
*
*/
#include "libcrypt.h"
static Key_exps *genKeyExps P((BigInt, BigInt, BigInt, int, BigInt));
static void chineseRemTheorem P((BigInt , RSAPrivateKey *, BigInt));
static void genPrimesFor3 P((int, BigInt, BigInt, BigInt, BigInt));
#ifdef K_AND_R
static Key_exps *
genKeyExps(p, q, e, ebits, randomStart)
BigInt p, q, e;
int ebits;
BigInt randomStart;
#else
static Key_exps *genKeyExps(BigInt p,
BigInt q,
BigInt e,
int ebits,
BigInt randomStart)
#endif
{
BigInt phi, p1, q1;
BigInt u1, ngcd, ignore;
Key_exps *exps;
int ebytes;
#ifdef DLLEXPORT
HGLOBAL handle = clib_malloc(sizeof(Key_exps));
exps = (Key_exps *)GlobalLock(handle);
exps->exp_handle = handle;
#else
exps = (Key_exps *)clib_malloc(sizeof(Key_exps));
#endif
p1 = bigInit(0);
q1 = bigInit(0);
phi = bigInit(0);
u1 = bigInit(0);
ngcd = bigInit(0);
ignore = bigInit(0);
if (e == NULL)
e = bigInit(3);
bigSubtract(p, one, p1);
bigSubtract(q, one, q1);
bigMultiply(p1, q1, phi);
freeBignum(p1);
freeBignum(q1);
/* Get public exponent, relatively prime to modulus. */
/* A by product of the extendedGcd calculation is the inverse
of e mod phi, which is d, the private exponent.
If e has been specified, skip this.
*/
if (e == NULL) {
if (ebits > 2) {
ebytes = (ebits/8) + (ebits%8? 1: 0);
if (randomStart == NULL) {
bigRand(ebytes, e, PSEUDO);
}
else {
bigCopy(randomStart, e);
}
if (EVEN(e))
bigAdd(e, one, e);
}
}
extendedGcd(e, phi, u1, ignore, ngcd);
while (bigCompare(ngcd, one) != 0) {
bigAdd(e, two, e);
extendedGcd(e, phi, u1, ignore, ngcd);
}
exps->d = u1;
exps->e = e;
freeBignum(phi);
freeBignum(ngcd);
freeBignum(ignore);
return exps;
}
#ifdef K_AND_R
_TYPE( RSAPublicKey * )
buildRSAPublicKey(e, n)
BigInt e, n;
#else
_TYPE( RSAPublicKey * ) buildRSAPublicKey(BigInt e,
BigInt n)
#endif
{
RSAPublicKey *pk;
#ifdef DLLEXPORT
HGLOBAL handle = clib_malloc(sizeof(RSAPublicKey));
pk = (RSAPublicKey *)GlobalLock(handle);
pk->pubkey_handle = handle;
#else
pk = (RSAPublicKey *)clib_malloc(sizeof(RSAPublicKey));
#endif
pk->publicExponent = e;
pk->modulus = n;
return pk;
}
#ifdef K_AND_R
_TYPE( RSAPrivateKey * )
buildRSAPrivateKey(e, d, p, q, dp, dq, c12)
BigInt e, d, p, q, dp, dq, c12;
#else
_TYPE( RSAPrivateKey * ) buildRSAPrivateKey(BigInt e,
BigInt d,
BigInt p,
BigInt q,
BigInt dp,
BigInt dq,
BigInt c12)
#endif
{
RSAPrivateKey *pk;
ChineseRemStruct *crt;
#ifdef DLLEXPORT
HGLOBAL crt_handle = clib_malloc(sizeof(ChineseRemStruct));
HGLOBAL handle = clib_malloc(sizeof(RSAPrivateKey));
crt = (ChineseRemStruct *)GlobalLock(crt_handle);
crt->crt_handle = crt_handle;
pk = (RSAPrivateKey *)GlobalLock(handle);
pk->privkey_handle = handle;
#else
crt = (ChineseRemStruct *)clib_malloc(sizeof(ChineseRemStruct));
pk = (RSAPrivateKey *)clib_malloc(sizeof(RSAPrivateKey));
#endif
pk->publicExponent = e;
pk->privateExponent = d;
pk->modulus = bigInit(0);
bigMultiply(p, q, pk->modulus);
pk->crt = crt;
pk->crt->p = p;
pk->crt->q = q;
pk->crt->dp = dp;
pk->crt->dq = dq;
pk->crt->c12 = c12;
return pk;
}
#ifdef K_AND_R
_TYPE( RSAKeySet * )
buildRSAKeySet(e, d, p, q)
BigInt e, d, p, q;
#else
_TYPE( RSAKeySet * ) buildRSAKeySet(BigInt e,
BigInt d,
BigInt p,
BigInt q)
#endif
{
BigInt pminus1, qminus1, n, dp, dq, c12;
BigInt ecopy, dcopy;
RSAKeySet *ks;
#ifdef DLLEXPORT
HGLOBAL ks_handle = clib_malloc(sizeof(RSAKeySet));
ks = (RSAKeySet *)GlobalLock(ks_handle);
ks->keyset_handle = ks_handle;
#else
ks = (RSAKeySet *)clib_malloc(sizeof(RSAKeySet));
#endif
n = bigInit(0);
bigMultiply(p, q, n);
ecopy = bigInit(0);
bigCopy(e, ecopy);
ks->publicKey = buildRSAPublicKey(ecopy, n);
pminus1 = bigInit(0);
qminus1 = bigInit(0);
bigSubtract(p, one, pminus1);
bigSubtract(q, one, qminus1);
dp = bigInit(0);
dq = bigInit(0);
bigMod(d, pminus1, dp);
bigMod(d, qminus1, dq);
c12 = bigInit(0);
getInverse(q, p, c12);
ecopy = bigInit(0);
bigCopy(e, ecopy);
dcopy = bigInit(0);
bigCopy(d, dcopy);
ks->privateKey = buildRSAPrivateKey(ecopy, dcopy, p, q,
dp, dq, c12);
freeBignum(pminus1);
freeBignum(qminus1);
return ks;
}
#ifdef K_AND_R
static void
genPrimesFor3(nbits, p, q, r1, r2)
int nbits;
BigInt p, q, r1, r2;
#else
static void genPrimesFor3(int nbits,
BigInt p,
BigInt q,
BigInt r1,
BigInt r2)
#endif
{
BigInt ngcd, ignore, three, pminus1, qminus1;
ignore = bigInit(0);
three = bigInit(3);
pminus1 = bigInit(0);
qminus1 = bigInit(0);
/* Gordon algorithm doesn't care about the p-1 factor size */
genStrongPrimeSet(nbits/2, p, (int)NULL, ignore, GORDON, r1);
bigSubtract(p, one, pminus1);
ngcd = gcd(three, pminus1);
while (bigCompare(ngcd, one) != 0) {
if (r1 != NULL)
randomize(r1);
freeBignum(ngcd);
genStrongPrimeSet(nbits/2, p, (int)NULL, ignore, GORDON, r1);
bigSubtract(p, one, pminus1);
ngcd = gcd(three, pminus1);
}
freeBignum(ngcd);
genStrongPrimeSet(nbits/2, q, (int)NULL, ignore, GORDON, r2);
bigSubtract(q, one, qminus1);
ngcd = gcd(three, qminus1);
while (bigCompare(ngcd, one) != 0) {
if (r2 != NULL)
randomize(r2);
freeBignum(ngcd);
genStrongPrimeSet(nbits/2, q, (int)NULL, ignore, GORDON, r2);
bigSubtract(q, one, qminus1);
ngcd = gcd(three, qminus1);
}
freeBignum(ngcd);
freeBignum(pminus1);
freeBignum(qminus1);
freeBignum(ignore);
freeBignum(three);
}
#ifdef K_AND_R
_TYPE( int )
randBytesNeededForRSA (modlen, ebits)
int modlen, ebits;
#else
_TYPE( int ) randBytesNeededForRSA (int modlen, int ebits)
#endif
{
int bytes;
bytes = ((modlen + ebits)/8) + ((modlen+ebits)%8? 1: 0);
return bytes;
}
#ifdef K_AND_R
_TYPE( RSAKeySet * )
genRSAKeySet(nbits, ebits, e, randomStart)
Ulong nbits, ebits, randomStart;
BigInt e;
#else
_TYPE( RSAKeySet * ) genRSAKeySet(int nbits,
int ebits,
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -