20060303a

1 files changed, 646 insertions, 0 deletions

diff --git a/include/libcrypt_o.h b/include/libcrypt_o.h
new file mode 100644
index 00000000..c6f1e778
--- /dev/null
+++ b/include/libcrypt_o.h
@@ -0,0 +1,646 @@
+#pragma	src	"/usr/inferno/libcrypt"
+
+#define NOSPOOKS
+
+/*
+ *  To use Brickell bigpow, uncomment the following and recompile everything:
+ *  #define BRICKELL
+ */
+
+/************************************************************************/
+/* system interface (can be overriden)	*/
+
+enum
+{
+	CRITICAL=	1,
+	WARNING=	0
+};
+
+void	handle_exception(int, char*);
+void	*crypt_malloc(int);
+void	crypt_free(void*);
+
+/************************************************************************/
+/* infinite precision integer arithmetic */
+
+/* The following all define the size of a basic unit math is performed on */
+typedef ulong NumType;
+#define NumTypeBits	(sizeof(NumType)*8)
+#define NumTypeMask	(ulong)0xFFFFFFFF
+typedef long		SignedNumType;
+typedef int		Boolean;
+typedef NumType		*BigData;
+
+enum
+{
+	TRUE=	1,
+	FALSE=	0
+};
+
+typedef int Sign;
+enum
+{
+	POS=	1,
+	NEG=	-1
+};
+
+
+/* Fundamental bigmath unit */
+typedef struct Bignum {
+	Sign sign;
+	ulong length; /* length of number (in NumType units)	*/
+	ulong space; /* storage space (in NumType units)	*/
+	NumType *num;
+} Bignum;
+typedef Bignum * BigInt;
+
+/* macros to get return properties of a big integer */
+#define NUM(x) ((x)->num)
+#define LENGTH(x) ((x)->length)
+#define SIGN(x) ((x)->sign)
+#define SPACE(x) ((x)->space)
+#define LENGTH_IN_BYTES(N) (((N + (NumTypeBits-1) / NumTypeBits) * sizeof(NumType))
+#define EVEN(a) (((NUM(a)[0] & 1) == 0) ? TRUE : FALSE)
+#define ODD(a) (((NUM(a)[0] & 1) != 0) ? TRUE : FALSE)
+#define BIT2BYTE 8
+/* Some predefined constants in bignum form. */
+#define ZERO(x) ((LENGTH(x) == 1) && (NUM(x)[0] == 0))
+#define ONE(x) ((LENGTH(x) == 1) && (NUM(x)[0] == 1))
+#define TWO(x) ((LENGTH(x) == 1) && (NUM(x)[0] == 2))
+
+/* GUARANTEE is the principal macro for bigint memory allocation.
+ * Space is updated by this macro.  If a bigint shrinks (say as the result
+ * of a modular reduction) space need not be freed.  The length will be reduced.
+ * If later the reduced number is squared (say) then we don't need to realloc
+ * the memory.  Look at bigmath.c to get a feel for how this is used.
+ */
+#define GUARANTEE(B,S) {\
+	if((B)->space < (S)) {\
+	(B)->space = (S);\
+	(B)->num = (BigData)realloc((uchar *)NUM(B), (unsigned)(sizeof(NumType)*SPACE(B)));\
+	memset((B)->num+LENGTH(B), 0, sizeof(NumType)*((S)-LENGTH(B)));\
+	}\
+}
+
+BigInt	atobig(char*);
+int	bigtostr(BigInt, char*, int, int);
+BigInt	strtobig(char*, char**, int);
+void	bigAdd(BigInt, BigInt, BigInt);
+void	bigAnd(BigInt, BigInt, BigInt);
+int	bigBits(BigInt);
+int	bigBytes(BigInt);
+int	bigCompare(BigInt, BigInt);
+int	bigconv(Fmt*);	/* %B */
+void	bigCopy(BigInt, BigInt);
+void	bigCube(BigInt, BigInt, BigInt);
+int	bigDivide(BigInt, BigInt, BigInt, BigInt);
+#define bigInit(x) (itobig((NumType)(x)))
+void	bigLeftShift(BigInt, int, BigInt);
+int	bigMod(BigInt, BigInt, BigInt);
+void	bigMultiply(BigInt, BigInt, BigInt);
+void	bigOr(BigInt, BigInt, BigInt);
+void	bigPow(BigInt, BigInt, BigInt, BigInt);
+void	bigRightShift(BigInt, int, BigInt);
+void	bigsquare(BigInt a, BigInt res);
+void	bigsub(BigInt, BigInt, BigInt);
+void	bigSubtract(BigInt, BigInt, BigInt);
+Sign	bigTest(BigInt);
+int	bigToBuf(BigInt big, int bufsize, uchar *buf);
+int	bigTobeBuf(BigInt big, int bufsize, uchar *buf);
+void	bigXor(BigInt, BigInt, BigInt);
+void	bufToBig(uchar *buf, int buflen, BigInt big);
+void	bebufToBig(uchar *buf, int buflen, BigInt big);
+void	crtCombine(BigInt, BigInt, BigInt, BigInt, BigInt, BigInt);
+Boolean	even(BigInt);
+void	freeBignum(BigInt);
+BigInt	itobig(NumType);
+void	lbigmult(BigInt a, BigInt b, BigInt res);
+NumType	msb(NumType);
+void	negate(BigInt, BigInt, BigInt);
+Boolean	odd(BigInt);
+void	reset_big(BigInt a, NumType val);
+void	trim(BigInt);
+
+/* always around */
+extern BigInt zero, one, two;
+
+/*********************************************************************/
+/* primes */
+
+enum
+{
+	NIST= 0,
+	GORDON= 1
+};
+typedef int PrimeType;
+
+void	setPrimeTestAttempts(int);
+Boolean	primeTest(BigInt);
+void	getPrime(int, BigInt);
+void	genStrongPrimeSet(int, BigInt, int, BigInt, PrimeType);
+void	genStrongPrime(int, BigInt);
+void	getPrimitiveElement(BigInt, BigInt, BigInt);
+
+/************************************************************************/
+/* random numbers */
+
+/* By default, REALLY ==> truerand() and PSEUDO ==> fsrRandom() */
+enum
+{
+	REALLY=	1,
+	PSEUDO= 0
+};
+typedef int RandType;
+
+void	bigRand(int, BigInt, RandType);
+void	bigReallyRand(int, BigInt);
+void	bigPseudoRand(int, BigInt);
+void	seed_fsr(uchar*, int);
+ulong	fsrRandom(void);
+void	getRandBetween(BigInt, BigInt, BigInt, RandType);
+int	randomBytes(uchar*, int, RandType);
+void	pseudoRandomBytes(uchar*, int);
+void	reallyRandomBytes(uchar*, int);
+
+ulong	truerand(void);
+ulong	fastrand(void);
+
+#ifdef PRAND
+#define seed_rng seed_prand
+#else
+#define seed_rng seed_fsr
+#endif
+
+/************************************************************************/
+/* aes */
+
+enum
+{
+	AESbsize=	16,
+	AESmaxkey=	32,
+	AESmaxrounds=	14
+};
+
+typedef struct AESstate AESstate;
+struct AESstate
+{
+	ulong	setup;
+	int	rounds;
+	int	keybytes;
+	uchar	key[AESmaxkey];		/* unexpanded key */
+	u32int	ekey[4*(AESmaxrounds + 1)];	/* encryption key */
+	u32int	dkey[4*(AESmaxrounds + 1)];	/* decryption key */
+	uchar	ivec[AESbsize];	/* initialization vector */
+};
+
+void	setupAESstate(AESstate *s, uchar key[], int keybytes, uchar *ivec);
+void	aesCBCencrypt(uchar *p, int len, AESstate *s);
+void	aesCBCdecrypt(uchar *p, int len, AESstate *s);
+
+
+/************************************************************************/
+/* rc4 */
+
+typedef struct RC4state RC4state;
+struct RC4state
+{
+	 uchar state[256];
+	 uchar x;
+	 uchar y;
+};
+
+void	setupRC4state(RC4state*, uchar*, int);
+void	rc4(RC4state*, uchar*, int);
+void	rc4skip(RC4state*, int);
+void	rc4back(RC4state*, int);
+
+/************************************************************************/
+/* idea */
+
+typedef struct IDEAstate IDEAstate;
+struct IDEAstate
+{
+	uchar	key[16];
+	ushort	edkey[104];
+	uchar	ivec[8];
+};
+
+void	setupIDEAstate(IDEAstate*, uchar*, uchar*);
+void	idea_key_setup(uchar*, ushort*);
+void	idea_cipher(ushort*, uchar*, int);
+
+/************************************************************************/
+/* des */
+
+enum
+{
+	DESbsize=	8,
+	IDEAbsize=	8,
+
+	ECB=		10,
+	CBC=		20,
+	OFM=		30
+
+};
+typedef int ModeType;
+
+/* des key conversion */
+uchar	*atodes(char*);
+int	desconv(va_list*, void*); /* %D */
+
+/* single des */
+typedef struct DESstate DESstate;
+struct DESstate
+{
+	ulong	setup;
+	uchar	key[8];		/* unexpanded key */
+	ulong	expanded[32];	/* expanded key */
+	uchar	ivec[8];	/* initialization vector */
+};
+
+void	setupDESstate(DESstate*, uchar*, uchar*);
+void	des_key_setup(uchar*, ulong*);
+void	block_cipher(ulong*, uchar*, int);
+
+/* The following functions are currently not used */
+void	key_setup(uchar*, ulong*);
+void	key_crunch(uchar*, int, uchar*);
+void	bCBCEncrypt(uchar*, uchar*, ulong*, int);
+void	blockECBEncrypt(uchar*, uchar*, DESstate*);
+void	bCBCDecrypt(uchar*, uchar*, ulong*, int);
+void	blockECBDecrypt(uchar*, uchar*, DESstate*);
+void	blockCBCEncrypt(uchar*, uchar*, uchar*, int, DESstate*);
+void	blockCBCDecrypt(uchar*, uchar*, uchar*, int, DESstate*);
+void	blockOFMEncrypt(uchar*, uchar*, uchar*, int, DESstate*);
+void	blockOFMDecrypt(uchar*, uchar*, uchar*, int, DESstate*);
+void	bufferECBEncrypt(uchar*, uchar*, int);
+void	bufferECBDecrypt(uchar*, uchar*, int);
+void	bufferCBCEncrypt(uchar*, uchar*, uchar*, int);
+void	bufferCBCDecrypt(uchar*, uchar*, uchar*, int);
+void	bufferOFMEncrypt(uchar*, uchar*, uchar*, int);
+void	bufferOFMDecrypt(uchar*, uchar*, uchar*, int);
+
+/* triple des */
+typedef struct DES3state DES3state;
+struct DES3state
+{
+	ulong	setup;
+	uchar	key[3][8];		/* unexpanded key */
+	ulong	expanded[3][32];	/* expanded key */
+	uchar	ivec[8];		/* initialization vector */
+};
+
+#define DES3D  1
+
+void	setupDES3state(DES3state*, uchar key[3][8], uchar*);
+void	triple_block_cipher(ulong keys[3][32], uchar*, int);
+
+/* The following functions are currently not used */
+void	b3CBCEncrypt(uchar*, uchar*, ulong int_key[3][32], int);
+void	block3ECBEncrypt(uchar*, uchar key[3][8], DES3state*);
+void	b3CBCDecrypt(uchar*, uchar*, ulong int_key[3][32], int);
+void	block3ECBDecrypt(uchar*, uchar key[3][8], DES3state*);
+void	block3CBCEncrypt(uchar*, uchar*, uchar key[3][8], int, DES3state*);
+void	block3CBCDecrypt(uchar*, uchar*, uchar key[3][8], int, DES3state*);
+void	block3OFMEncrypt(uchar*, uchar*, uchar key[3][8], int, DES3state*);
+void	block3OFMDecrypt(uchar*, uchar*, uchar key[3][8], int, DES3state*);
+void	buffer3ECBEncrypt(uchar *buf, uchar key[3][8], int);
+void	buffer3ECBDecrypt(uchar *buf, uchar key[3][8], int);
+void	buffer3CBCEncrypt(uchar *buf, uchar*, uchar key[3][8], int);
+void	buffer3CBCDecrypt(uchar *buf, uchar*, uchar key[3][8], int);
+void	buffer3OFMEncrypt(uchar *buf, uchar*, uchar key[3][8], int);
+void	buffer3OFMDecrypt(uchar *buf, uchar*, uchar key[3][8], int);
+void	mbitCFMEncrypt(uchar*, uchar*, ulong*, int);
+void	mbitCFMDecrypt(uchar*, uchar*, ulong*, int m);
+
+/************************************************************************/
+/* digests */
+
+enum
+{
+	SHAdlen=	20,	/* SHA digest length */
+	SHA1dlen = SHAdlen,
+	MD4dlen=	16,	/* MD4 digest length */
+	MD5dlen=	16	/* MD5 digest length */
+};
+
+typedef struct DigestState DigestState;
+struct DigestState
+{
+	ulong len;
+	ulong state[5];
+	uchar buf[128];
+	int blen;
+	char malloced;
+	char seeded;
+};
+typedef struct DigestState SHAstate;
+typedef struct DigestState SHA1state;
+typedef struct DigestState MD5state;
+typedef struct DigestState MD4state;
+
+DigestState* md4(uchar*, ulong, uchar*, DigestState*);
+DigestState* md5(uchar*, ulong, uchar*, DigestState*);
+DigestState* sha1(uchar*, ulong, uchar*, DigestState*);
+
+DigestState* hmac_md5(uchar*, ulong, uchar*, ulong, uchar*, DigestState*);
+DigestState* hmac_sha1(uchar*, ulong, uchar*, ulong, uchar*, DigestState*);
+
+/************************************************************************/
+
+/*	#include "bigpow.h"	*/
+
+typedef struct {
+	unsigned length;
+	BigInt t[2];
+} Table;
+
+typedef struct {
+	BigInt N;
+	NumType n0p;
+} Mont_set;
+
+/* Struct for Montgomery reduction REDC */
+
+/* Generally no reason to play with this stuff, used exclusively within bigPow */
+NumType		modInverse(NumType);
+Mont_set	*mont_set(BigInt);
+BigInt		res_form(BigInt big, Mont_set *ms);
+
+/* When doing a^b mod c for a constant a and c, a table can be created using the following
+ * function.  This is useful in El Gamal variants where the base (a) and the modulus are
+ * constant in groupd of keys.  This is true of DSA (an El Gamal variant) as well.
+ */
+Table		*g16_bigpow(BigInt a, BigInt modulus, NumType explength);
+
+/* bigpow using table: Ernie Brickell's method. */
+void		brickell_bigpow(Table *table,
+	   			BigInt exponent,
+	   			BigInt modulus,
+	   			BigInt result);
+
+void		freeTable(Table *);
+void		freeMs(Mont_set *);
+
+/************************************************************************/
+
+
+/*	#include "longmult.h"	*/
+/* Not part of the cryptoLib interface - low level multiplication routines. */
+NumType	smult(NumType *, NumType, NumType *, int);
+NumType	LMULT(NumType *, NumType, NumType *, int);
+void	BUILDDIAG(NumType *, NumType *, int);
+void	SQUAREINNERLOOP(NumType *, NumType, NumType *, int, int);
+
+/************************************************************************/
+
+
+/*	#include "coremult.h"	*/
+/* Not part of the cryptoLib interface - low level multiplication routines. */
+void	numtype_bigmult2(NumType *, NumType *, NumType *);
+void	numtype_bigmult8(NumType *, NumType *, NumType *);
+void	numtype_bigmultN(NumType *, NumType *, NumType *, int);
+void	numtype_bigsquareN(NumType *, NumType *, int);
+void	bigmult4(BigData, BigData, BigData);
+void	bigmult8(BigData, BigData, BigData);
+void	bigmultN(BigData, BigData, BigData, int);
+void	bigsquare8(BigData, BigData);
+void	bigsquareN(BigData, BigData, int);
+void	numtype_bigmult(BigInt, NumType, BigInt, int);
+void	REDC(BigInt, Mont_set *);
+
+/************************************************************************/
+
+
+/*	#include "euclid.h"	*/
+/* Euclid's extended gcd algorithm for solving
+ * ax + by = gcd(a, b)
+ */
+void extendedGcd(BigInt a,
+	       BigInt b,
+	       BigInt x,
+	       BigInt y,
+	       BigInt gcd);
+
+/* If gcd(a, b) = 1, x = inverse of a (mod b) and y = inverse of b (mod a) */
+void getInverse(BigInt a,
+	      BigInt b,
+	      BigInt inverse_of_a_mod_b );
+
+BigInt gcd(BigInt a, BigInt b);
+
+/************************************************************************/
+
+/*	#include "jacobi.h"	*/
+/* calculate the jacobi symbol (a/b) */
+int bigJacobi(BigInt a,
+	    BigInt b);
+
+int jacobi(int a,
+	 int b);
+
+/* Return true if a is a quadratic residue mod p*q where p and q are prime. */
+int bigIsQR(BigInt a,
+	  BigInt p,
+	  BigInt q);
+int isQR(int a,
+	       int p,
+	       int q);
+
+/************************************************************************/
+/* quadratic residues */
+
+/* Return true if a is a quadratic residue mod p */
+Boolean quadResidue(BigInt a,
+	  BigInt p);
+
+/* Return true if a is a quadratic residue mod p*q where p and q are prime. */
+Boolean compositeQuadResidue(BigInt a,
+	   BigInt p,
+	   BigInt q);
+
+/* return the square root of a (mod p) where p is prime. */
+void squareRoot(BigInt a,
+	      BigInt p,
+	      BigInt result);
+
+/* return the 2 linearly independent square roots of a (mod p*q) for p and q prime. */
+/* The other 2 roots are n-root1 and n-root2 */
+void compositeSquareRoot(BigInt a,
+	       BigInt p,
+	       BigInt q,
+	       BigInt root1,
+	       BigInt root2);
+
+/************************************************************************/
+/* El Gamal Crypto system stuff */
+
+/* p is prime, q is a large prime factor of p-1.  alpha is the base
+ * g_table is included as part of the key to enable Brickell exponentiation.
+ * If one set {p, q, alpha} is used by "everyone" then this table can be constant.
+ * That is, {p, q, alpha, g_table} is public.  The private key is then
+ * the exponent (or secret) and the public key is alpha^exponent mod p.
+ */
+typedef struct EGParams {
+	BigInt p, q, alpha;
+} EGParams;
+
+typedef struct EGPrivateKey {
+	BigInt p, q;
+	BigInt alpha;
+	BigInt publicKey;
+	BigInt secret;
+	Table *g_table;
+} EGPrivateKey;
+
+typedef struct EGPublicKey {
+	BigInt p, q;
+	BigInt alpha;
+	BigInt publicKey;
+	Table *g_table, *y_table;
+} EGPublicKey;
+
+typedef struct EGKeySet {
+	EGPublicKey *publicKey;
+	EGPrivateKey *privateKey;
+} EGKeySet;
+
+typedef struct EGSignature {
+	BigInt r, s;
+} EGSignature;
+
+/* generate global p, q, and alpha */
+EGParams * genEGParams(int, int);
+
+/* generate alpha and p numbits long */
+void genDiffieHellmanSet(BigInt p,
+	       BigInt alpha,
+	       int pbits,
+	       int qbits);
+
+/* generate public and private keys corresponding to params */
+EGKeySet * genEGKeySet(EGParams *params);
+
+/* generate private key */
+EGPrivateKey * genEGPrivateKey(EGParams *params);
+
+/* El Gamal signature */
+void * EGSign(BigInt big,
+	   void *key);
+
+/* Verify signature of big */
+Boolean EGVerify(BigInt big,
+	       void *sig,
+	       void *key);
+
+/* El Gamal encrypt and decrypt functions -- these are not reversible as in RSA 
+ * That is, Decrypt(Encrypt(m, pubkey), privkey) is NOT the same as
+ * Encrypt(Decrypt(m, privkey), pubkey).  This symmetry doesn't exist with
+ * El Gamal.
+ */
+BigInt EGEncrypt(BigInt, EGPublicKey *);
+
+BigInt EGDecrypt(BigInt, EGPrivateKey *);
+
+/* El Gamal Cleanup functions -- be sure to use these! */
+void freeEGPublicKey(void *);
+void freeEGPrivateKey(void *);
+void freeEGKeys(EGKeySet *);
+void freeEGSig(void *);
+void freeEGParams(EGParams *);
+
+/************************************************************************/
+/* DSS == modified Elgamal */
+
+/* The digital signature standard doesn't introduce new structures...we reuse the
+ * El Gamal structs and parameter generation stuff.
+ */
+typedef EGSignature DSSSignature;
+typedef EGPublicKey DSSPublicKey;
+typedef EGPrivateKey DSSPrivateKey;
+typedef EGParams DSSParams;
+typedef EGKeySet DSSKeySet;
+
+void *DSSSign(BigInt big, void *key);
+
+Boolean DSSVerify(BigInt big, void *sig, void *key);
+
+#define genDSSParams genEGParams
+#define genDSSKeySet genEGKeySet
+#define genDSSPrivateKey genEGPrivateKey
+void freeDSSSig(void *);
+#define freeDSSPublicKey freeEGPublicKey
+#define freeDSSPrivateKey freeEGPrivateKey
+#define freeDSSKeys freeEGKeys
+#define freeDSSParams freeEGParams
+
+/************************************************************************/
+/* base 64 conversions */
+
+int dec64(uchar *out, int lim, char *in, int n);
+int enc64(char *out, int lim, uchar *in, int n);
+
+/************************************************************************/
+/* RSA Cryptosystem stuff */
+
+/* The private key contains material to enable the Chinese Remainder speedup
+ * of decryption (or signing).  For RSA,
+ * Decrypt(Encrypt(m, pubkey), privkey) = Encrypt(Decrypt(m, privkey), pubkey) = m
+ */
+typedef struct Key_exps {
+	BigInt e;
+	BigInt d;
+} Key_exps;
+
+typedef struct ChineseRemStruct {
+	BigInt p, q;    /* SECRET primes */
+	BigInt dp, dq;  /* d mod p, d mod q */
+	BigInt c12;     /* inverse of p (mod q) */
+} ChineseRemStruct;
+
+typedef struct RSAPublicKey {
+	BigInt publicExponent;
+	BigInt modulus;
+} RSAPublicKey;
+
+typedef struct RSAPrivateKey {
+	BigInt publicExponent;
+	BigInt privateExponent;  /* SECRET */
+	BigInt modulus;
+	ChineseRemStruct *crt;   /* SECRET */
+} RSAPrivateKey;
+
+typedef struct RSAKeySet {
+	RSAPublicKey *publicKey;
+	RSAPrivateKey *privateKey;
+} RSAKeySet;
+
+typedef Bignum RSASignature;
+
+/* generate an RSA key set with modulus length = modbits and
+ * public exponent length = explen.  If explen = 2, the public exponent = 3.
+ */
+RSAKeySet * genRSAKeySet(int, int);
+void freeRSAPublicKey(void *);
+void freeRSAPrivateKey(void *);
+void freeRSAKeys(RSAKeySet *);
+void freeRSASig(void *);
+
+/* RSA Encryption(m) = m^publicExponent mod modulus */
+BigInt RSAEncrypt(BigInt msg,
+	RSAPublicKey *key);
+
+/* RSA Decryption = m^privateExponent mod modulus */
+BigInt RSADecrypt(BigInt msg,
+	RSAPrivateKey *key);
+
+/* Signing is just RSADecrypt */
+void * RSASign(BigInt msg, void *key);
+
+/* Verifying is just RSAEncrypt */
+Boolean RSAVerify(BigInt msg,
+	void *sig,
+	void *key);
+
+#pragma	varargck	type	"B"	Bignum*
+#pragma	varargck	type	"U"	Bignum*