请问谁有RSA加密算法的Delphi源程序，300分相送(300分)

如题

http://www.programsalon.com/down_top.asp

楼上的兄弟，你给的地址需要购买呀，不能下载，能否贴出来，谢谢

我有全套经典加密算法的pascal版本,老实说很多都是我自己改写的,
,经过严格的测试的!!!有意向的朋友可以联系哦,不过我明年才有时间发给你们!
解密算法大部分也有的,不过这个可得收费了!呵呵,好歹也搞了我1,2年时间了,
价格可以商量!windows操作系统大部分加密算法的解密都可搞定的!!搞不定的
不要钱!

加密算法是自由交流的!有意向者先跟我联系哟!
不过现在忙于人生最大的事情,所以明年才有时间发给你们!(资料都丢在家里了)
另外还有我自己写的一个加密算法,强度我个人认为不比一些经典算法差劲,
欢迎明年大家帮忙测试一下强度!

我也需要，谢谢哪位大虾，能给我一份吗？

GZ

http://ace.ulyssis.student.kuleuven.ac.be/~triade/GInt/bin/RSA.zip

请不久好像有人还发了一个控件，还带有例子，我收到过
就在这个论坛

谢谢zw84611

/*
RSA.C - RSA routines for RSAEURO

Copyright (c) J.S.A.Kapp 1994 - 1995.

RSAEURO - RSA Library compatible with RSAREF(tm) 2.0.

All functions prototypes are the Same as for RSAREF(tm).
To aid compatiblity the source and the files follow the
same naming comventions that RSAREF(tm) uses. This should aid
direct importing to your applications.

This library is legal everywhere outside the US. And should
NOT be imported to the US and used there.

All Trademarks Acknowledged.

RSA encryption performed as defined in the PKCS (#1) by RSADSI.

Revision history
0.90 First revision, code produced very similar to that
of RSAREF(tm), still it worked fine.

0.91 Current revision, code altered to aid speeding up.
Used pointer accesses to arrays to speed up some parts,
mainly during the loops.
*/

#include "rsaeuro.h"
#include "r_random.h"
#include "rsa.h"
#include "nn.h"

static int rsapublicfunc PROTO_LIST((unsigned char *, unsigned int *, unsigned char *, unsigned int, R_RSA_PUBLIC_KEY *));
static int rsaprivatefunc PROTO_LIST((unsigned char *, unsigned int *, unsigned char *, unsigned int, R_RSA_PRIVATE_KEY *));

/* RSA encryption, according to RSADSI's PKCS #1. */

int RSAPublicEncrypt(output, outputLen, input, inputLen, publicKey, randomStruct)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PUBLIC_KEY *publicKey; /* RSA public key */
R_RANDOM_STRUCT *randomStruct; /* random structure */
{
int status;
unsigned char byte, pkcsBlock[MAX_RSA_MODULUS_LEN];
unsigned int i, modulusLen;

modulusLen = (publicKey->bits + 7) / 8;

if(inputLen + 11 > modulusLen)
return(RE_LEN);

*pkcsBlock = 0; /* PKCS Block Makeup */

/* block type 2 */
*(pkcsBlock+1) = 2;

for(i = 2; i < modulusLen - inputLen - 1; i++) {
/* Find nonzero random byte. */
do { /* random bytes used to pad the PKCS Block */
R_GenerateBytes(&byte, 1, randomStruct);
}while(byte == 0);
*(pkcsBlock+i) = byte;
}
/* separator */
pkcsBlock[i++] = 0;

R_memcpy((POINTER)&pkcsBlock, (POINTER)input, inputLen);

status = rsapublicfunc(output, outputLen, pkcsBlock, modulusLen, publicKey);

/* Clear sensitive information. */

byte = 0;
R_memset((POINTER)pkcsBlock, 0, sizeof(pkcsBlock));

return(status);
}

/* RSA decryption, according to RSADSI's PKCS #1. */

int RSAPublicDecrypt(output, outputLen, input, inputLen, publicKey)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PUBLIC_KEY *publicKey; /* RSA public key */
{
int status;
unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
unsigned int i, modulusLen, pkcsBlockLen;

modulusLen = (publicKey->bits + 7) / 8;

if(inputLen > modulusLen)
return(RE_LEN);

status = rsapublicfunc(pkcsBlock, &pkcsBlockLen, input, inputLen, publicKey);
if(status)
return(status);

if(pkcsBlockLen != modulusLen)
return(RE_LEN);

/* Require block type 1. */

if((pkcsBlock[0] != 0) || (pkcsBlock[1] != 1))
return(RE_DATA);

for(i = 2; i < modulusLen-1; i++)
if(*(pkcsBlock+i) != 0xff)
break;

/* separator check */

if(pkcsBlock[i++] != 0)
return(RE_DATA);

*outputLen = modulusLen - i;

if(*outputLen + 11 > modulusLen)
return(RE_DATA);

R_memcpy((POINTER)output, (POINTER)&pkcsBlock, *outputLen);

/* Clear sensitive information. */

R_memset((POINTER)pkcsBlock, 0, sizeof(pkcsBlock));

return(IDOK);
}

/* RSA encryption, according to RSADSI's PKCS #1. */

int RSAPrivateEncrypt(output, outputLen, input, inputLen, privateKey)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PRIVATE_KEY *privateKey; /* RSA private key */
{
int status;
unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
unsigned int i, modulusLen;

modulusLen = (privateKey->bits + 7) / 8;

if(inputLen + 11 > modulusLen)
return (RE_LEN);

*pkcsBlock = 0;
/* block type 1 */
*(pkcsBlock+1) = 1;

for (i = 2; i < modulusLen - inputLen - 1; i++)
*(pkcsBlock+i) = 0xff;

/* separator */
pkcsBlock[i++] = 0;

R_memcpy((POINTER)&pkcsBlock, (POINTER)input, inputLen);

status = rsaprivatefunc(output, outputLen, pkcsBlock, modulusLen, privateKey);

/* Clear sensitive information. */

R_memset((POINTER)pkcsBlock, 0, sizeof(pkcsBlock));

return(status);
}

/* RSA decryption, according to RSADSI's PKCS #1. */

int RSAPrivateDecrypt(output, outputLen, input, inputLen, privateKey)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PRIVATE_KEY *privateKey; /* RSA private key */
{
int status;
unsigned char pkcsBlock[MAX_RSA_MODULUS_LEN];
unsigned int i, modulusLen, pkcsBlockLen;

modulusLen = (privateKey->bits + 7) / 8;

if(inputLen > modulusLen)
return (RE_LEN);

status = rsaprivatefunc(pkcsBlock, &pkcsBlockLen, input, inputLen, privateKey);
if(status)
return (status);

if(pkcsBlockLen != modulusLen)
return (RE_LEN);

/* We require block type 2. */

if((*pkcsBlock != 0) || (*(pkcsBlock+1) != 2))
return (RE_DATA);

for(i = 2; i < modulusLen-1; i++)
/* separator */
if (*(pkcsBlock+i) == 0)
break;

i++;
if(i >= modulusLen)
return(RE_DATA);

*outputLen = modulusLen - i;

if(*outputLen + 11 > modulusLen)
return(RE_DATA);

R_memcpy((POINTER)output, (POINTER)&pkcsBlock, *outputLen);

/* Clear sensitive information. */
R_memset((POINTER)pkcsBlock, 0, sizeof(pkcsBlock));

return(IDOK);
}

/* Raw RSA public-key operation. Output has same length as modulus.

Requires input < modulus.
*/
static int rsapublicfunc(output, outputLen, input, inputLen, publicKey)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PUBLIC_KEY *publicKey; /* RSA public key */
{
NN_DIGIT c[MAX_NN_DIGITS], e[MAX_NN_DIGITS], m[MAX_NN_DIGITS],
n[MAX_NN_DIGITS];
unsigned int eDigits, nDigits;


/* decode the required RSA function input data */
NN_Decode(m, MAX_NN_DIGITS, input, inputLen);
NN_Decode(n, MAX_NN_DIGITS, publicKey->modulus, MAX_RSA_MODULUS_LEN);
NN_Decode(e, MAX_NN_DIGITS, publicKey->exponent, MAX_RSA_MODULUS_LEN);

nDigits = NN_Digits(n, MAX_NN_DIGITS);
eDigits = NN_Digits(e, MAX_NN_DIGITS);

if(NN_Cmp(m, n, nDigits) >= 0)
return(RE_DATA);

*outputLen = (publicKey->bits + 7) / 8;

/* Compute c = m^e mod n. To perform actual RSA calc.*/

NN_ModExp (c, m, e, eDigits, n, nDigits);

/* encode output to standard form */
NN_Encode (output, *outputLen, c, nDigits);

/* Clear sensitive information. */

R_memset((POINTER)c, 0, sizeof(c));
R_memset((POINTER)m, 0, sizeof(m));

return(IDOK);
}

/* Raw RSA private-key operation. Output has same length as modulus.

Requires input < modulus.
*/

static int rsaprivatefunc(output, outputLen, input, inputLen, privateKey)
unsigned char *output; /* output block */
unsigned int *outputLen; /* length of output block */
unsigned char *input; /* input block */
unsigned int inputLen; /* length of input block */
R_RSA_PRIVATE_KEY *privateKey; /* RSA private key */
{
NN_DIGIT c[MAX_NN_DIGITS], cP[MAX_NN_DIGITS], cQ[MAX_NN_DIGITS],
dP[MAX_NN_DIGITS], dQ[MAX_NN_DIGITS], mP[MAX_NN_DIGITS],
mQ[MAX_NN_DIGITS], n[MAX_NN_DIGITS], p[MAX_NN_DIGITS], q[MAX_NN_DIGITS],
qInv[MAX_NN_DIGITS], t[MAX_NN_DIGITS];
unsigned int cDigits, nDigits, pDigits;

/* decode required input data from standard form */
NN_Decode(c, MAX_NN_DIGITS, input, inputLen); /* input */

/* private key data */
NN_Decode(p, MAX_NN_DIGITS, privateKey->prime[0], MAX_RSA_PRIME_LEN);
NN_Decode(q, MAX_NN_DIGITS, privateKey->prime[1], MAX_RSA_PRIME_LEN);
NN_Decode(dP, MAX_NN_DIGITS, privateKey->primeExponent[0], MAX_RSA_PRIME_LEN);
NN_Decode(dQ, MAX_NN_DIGITS, privateKey->primeExponent[1], MAX_RSA_PRIME_LEN);
NN_Decode(n, MAX_NN_DIGITS, privateKey->modulus, MAX_RSA_MODULUS_LEN);
NN_Decode(qInv, MAX_NN_DIGITS, privateKey->coefficient, MAX_RSA_PRIME_LEN);
/* work out lengths of input components */

cDigits = NN_Digits(c, MAX_NN_DIGITS);
pDigits = NN_Digits(p, MAX_NN_DIGITS);
nDigits = NN_Digits(n, MAX_NN_DIGITS);


if(NN_Cmp(c, n, nDigits) >= 0)
return(RE_DATA);

*outputLen = (privateKey->bits + 7) / 8;

/* Compute mP = cP^dP mod p and mQ = cQ^dQ mod q. (Assumes q has
length at most pDigits, i.e., p > q.)
*/

NN_Mod(cP, c, cDigits, p, pDigits);
NN_Mod(cQ, c, cDigits, q, pDigits);

NN_AssignZero(mP, nDigits);
NN_ModExp(mP, cP, dP, pDigits, p, pDigits);

NN_AssignZero(mQ, nDigits);
NN_ModExp(mQ, cQ, dQ, pDigits, q, pDigits);

/* Chinese Remainder Theorem:
m = ((((mP - mQ) mod p) * qInv) mod p) * q + mQ.
*/

if(NN_Cmp(mP, mQ, pDigits) >= 0) {
NN_Sub(t, mP, mQ, pDigits);
}else{
NN_Sub(t, mQ, mP, pDigits);
NN_Sub(t, p, t, pDigits);
}

NN_ModMult(t, t, qInv, p, pDigits);
NN_Mult(t, t, q, pDigits);
NN_Add(t, t, mQ, nDigits);

/* encode output to standard form */
NN_Encode (output, *outputLen, t, nDigits);

/* Clear sensitive information. */
/*
R_memset((POINTER)c, 0, sizeof(c));
R_memset((POINTER)cP, 0, sizeof(cP));
R_memset((POINTER)cQ, 0, sizeof(cQ));
R_memset((POINTER)dP, 0, sizeof(dP));
R_memset((POINTER)dQ, 0, sizeof(dQ));
R_memset((POINTER)mP, 0, sizeof(mP));
R_memset((POINTER)mQ, 0, sizeof(mQ));
R_memset((POINTER)p, 0, sizeof(p));
R_memset((POINTER)q, 0, sizeof(q));
R_memset((POINTER)qInv, 0, sizeof(qInv));
R_memset((POINTER)t, 0, sizeof(t));
*/
return(IDOK);
}

/*
RSA.H - header file for RSA.C

Copyright (c) J.S.A.Kapp 1994 - 1995.

RSAEURO - RSA Library compatible with RSAREF(tm) 2.0.

All functions prototypes are the Same as for RSAREF(tm).
To aid compatiblity the source and the files follow the
same naming comventions that RSAREF(tm) uses. This should aid
direct importing to your applications.

This library is legal everywhere outside the US. And should
NOT be imported to the US and used there.

All Trademarks Acknowledged.

RSA Routines Header File.

Revision 1.00 - JSAK 23/6/95, Final Release Version
*/

int RSAPublicEncrypt PROTO_LIST ((unsigned char *, unsigned int *, unsigned char *, unsigned int,
R_RSA_PUBLIC_KEY *, R_RANDOM_STRUCT *));
int RSAPrivateEncrypt PROTO_LIST ((unsigned char *, unsigned int *, unsigned char *, unsigned int,
R_RSA_PRIVATE_KEY *));
int RSAPublicDecrypt PROTO_LIST ((unsigned char *, unsigned int *, unsigned char *, unsigned int,
R_RSA_PUBLIC_KEY *));
int RSAPrivateDecrypt PROTO_LIST ((unsigned char *, unsigned int *, unsigned char *, unsigned int,
R_RSA_PRIVATE_KEY *));

C语言的RSA源程序在这里有下载：http://www.playicq.com/dispdoc.php?t=&id=1107

以上是C版本的，我从网上刚找到的！
Pascal的，是我自己修改的，资料不在身边，明年献上了！

/*
NN.C - natural numbers routines

Copyright (c) J.S.A.Kapp 1994 - 1995.

RSAEURO - RSA Library compatible with RSAREF(tm) 2.0.

All functions prototypes are the Same as for RSAREF(tm).
To aid compatiblity the source and the files follow the
same naming comventions that RSAREF(tm) uses. This should aid
direct importing to you applications.

This library is legal everywhere outside the US. And should
NOT be imported to the US and used there.

All Trademarks Acknowledged.

Revision hisitory
0.90 First revision, this revision was the basic routines.
Routines slower than final revision.

0.91 Second revision, this is the current revision, all
routines have been altered for speed increases. Also the
addition of assembler equivalents.
*/

#include "rsaeuro.h"
#include "nn.h"

/* internal static functions */

static NN_DIGIT subdigitmult PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT, NN_DIGIT *, unsigned int));

static void dmult PROTO_LIST ((NN_DIGIT, NN_DIGIT, NN_DIGIT *, NN_DIGIT *));

static unsigned int NN_DigitBits PROTO_LIST ((NN_DIGIT));

#ifndef USEASM
/* Decodes character string b into a, where character string is ordered
from most to least significant.

Lengths: a[digits], b[len].
Assumes b = 0 for i < len - digits * NN_DIGIT_LEN. (Otherwise most
significant bytes are truncated.)
*/
void NN_Decode (a, digits, b, len)
NN_DIGIT *a;
unsigned char *b;
unsigned int digits, len;
{
NN_DIGIT t;
int j;
unsigned int i, u;

for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
t = 0;
for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
t |= ((NN_DIGIT)b[j]) << u;
a = t;
}

for (; i < digits; i++)
a = 0;
}

/* Encodes b into character string a, where character string is ordered
from most to least significant.

Lengths: a[len], b[digits].
Assumes NN_Bits (b, digits) <= 8 * len. (Otherwise most significant
digits are truncated.)
*/
void NN_Encode (a, len, b, digits)
NN_DIGIT *b;
unsigned char *a;
unsigned int digits, len;
{
NN_DIGIT t;
int j;
unsigned int i, u;

for (i = 0, j = len - 1; i < digits && j >= 0; i++) {
t = b;
for (u = 0; j >= 0 && u < NN_DIGIT_BITS; j--, u += 8)
a[j] = (unsigned char)(t >> u);
}

for (; j >= 0; j--)
a[j] = 0;
}

/* Assigns a = 0. */

void NN_AssignZero (a, digits)
NN_DIGIT *a;
unsigned int digits;
{
if(digits) {
do {
*a++ = 0;
}while(--digits);
}
}

#endif

/* Assigns a = 2^b.

Lengths: a[digits].
Requires b < digits * NN_DIGIT_BITS.
*/
void NN_Assign2Exp (a, b, digits)
NN_DIGIT *a;
unsigned int b, digits;
{
NN_AssignZero (a, digits);

if (b >= digits * NN_DIGIT_BITS)
return;

a[b / NN_DIGIT_BITS] = (NN_DIGIT)1 << (b % NN_DIGIT_BITS);
}

/* Computes a = b - c. Returns borrow.

Lengths: a[digits], b[digits], c[digits].
*/
NN_DIGIT NN_Sub (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
NN_DIGIT temp, borrow = 0;

if(digits)
do {
if((temp = (*b++) - borrow) == MAX_NN_DIGIT)
temp = MAX_NN_DIGIT - *c++;
else
if((temp -= *c) > (MAX_NN_DIGIT - *c++))
borrow = 1;
else
borrow = 0;
*a++ = temp;
}while(--digits);

return(borrow);
}

/* Computes a = b * c.

Lengths: a[2*digits], b[digits], c[digits].
Assumes digits < MAX_NN_DIGITS.
*/

void NN_Mult (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
NN_DIGIT t[2*MAX_NN_DIGITS];
NN_DIGIT dhigh, dlow, carry;
unsigned int bDigits, cDigits, i, j;

NN_AssignZero (t, 2 * digits);

bDigits = NN_Digits (b, digits);
cDigits = NN_Digits (c, digits);

for (i = 0; i < bDigits; i++) {
carry = 0;
if(*(b+i) != 0) {
for(j = 0; j < cDigits; j++) {
dmult(*(b+i), *(c+j), &dhigh, &dlow);
if((*(t+(i+j)) = *(t+(i+j)) + carry) < carry)
carry = 1;
else
carry = 0;
if((*(t+(i+j)) += dlow) < dlow)
carry++;
carry += dhigh;
}
}
*(t+(i+cDigits)) += carry;
}


NN_Assign(a, t, 2 * digits);
}

/* Computes a = b * 2^c (i.e., shifts left c bits), returning carry.

Requires c < NN_DIGIT_BITS. */

NN_DIGIT NN_LShift (a, b, c, digits)
NN_DIGIT *a, *b;
unsigned int c, digits;
{
NN_DIGIT temp, carry = 0;
unsigned int t;

if(c < NN_DIGIT_BITS)
if(digits) {

t = NN_DIGIT_BITS - c;

do {
temp = *b++;
*a++ = (temp << c) | carry;
carry = c ? (temp >> t) : 0;
}while(--digits);
}

return (carry);
}

/* Computes a = c div 2^c (i.e., shifts right c bits), returning carry.

Requires: c < NN_DIGIT_BITS. */

NN_DIGIT NN_RShift (a, b, c, digits)
NN_DIGIT *a, *b;
unsigned int c, digits;
{
NN_DIGIT temp, carry = 0;
unsigned int t;

if(c < NN_DIGIT_BITS)
if(digits) {

t = NN_DIGIT_BITS - c;

do {
digits--;
temp = *(b+digits);
*(a+digits) = (temp >> c) | carry;
carry = c ? (temp << t) : 0;
}while(digits);
}

return (carry);
}

/* Computes a = c div d and b = c mod d.

Lengths: a[cDigits], b[dDigits], c[cDigits], d[dDigits].
Assumes d > 0, cDigits < 2 * MAX_NN_DIGITS,
dDigits < MAX_NN_DIGITS.
*/

void NN_Div (a, b, c, cDigits, d, dDigits)
NN_DIGIT *a, *b, *c, *d;
unsigned int cDigits, dDigits;
{
NN_DIGIT ai, cc[2*MAX_NN_DIGITS+1], dd[MAX_NN_DIGITS], s;
NN_DIGIT t[2], u, v, *ccptr;
NN_HALF_DIGIT aHigh, aLow, cHigh, cLow;
int i;
unsigned int ddDigits, shift;

ddDigits = NN_Digits (d, dDigits);
if(ddDigits == 0)
return;

shift = NN_DIGIT_BITS - NN_DigitBits (d[ddDigits-1]);
NN_AssignZero (cc, ddDigits);
cc[cDigits] = NN_LShift (cc, c, shift, cDigits);
NN_LShift (dd, d, shift, ddDigits);
s = dd[ddDigits-1];

NN_AssignZero (a, cDigits);

for (i = cDigits-ddDigits; i >= 0; i--) {
if (s == MAX_NN_DIGIT)
ai = cc[i+ddDigits];
else {
ccptr = &cc[i+ddDigits-1];

s++;
cHigh = (NN_HALF_DIGIT)HIGH_HALF (s);
cLow = (NN_HALF_DIGIT)LOW_HALF (s);

*t = *ccptr;
*(t+1) = *(ccptr+1);

if (cHigh == MAX_NN_HALF_DIGIT)
aHigh = (NN_HALF_DIGIT)HIGH_HALF (*(t+1));
else
aHigh = (NN_HALF_DIGIT)(*(t+1) / (cHigh + 1));
u = (NN_DIGIT)aHigh * (NN_DIGIT)cLow;
v = (NN_DIGIT)aHigh * (NN_DIGIT)cHigh;
if ((*t -= TO_HIGH_HALF (u)) > (MAX_NN_DIGIT - TO_HIGH_HALF (u)))
t[1]--;
*(t+1) -= HIGH_HALF (u);
*(t+1) -= v;

while ((*(t+1) > cHigh) ||
((*(t+1) == cHigh) && (*t >= TO_HIGH_HALF (cLow)))) {
if ((*t -= TO_HIGH_HALF (cLow)) > MAX_NN_DIGIT - TO_HIGH_HALF (cLow))
t[1]--;
*(t+1) -= cHigh;
aHigh++;
}

if (cHigh == MAX_NN_HALF_DIGIT)
aLow = (NN_HALF_DIGIT)LOW_HALF (*(t+1));
else
aLow =
(NN_HALF_DIGIT)((TO_HIGH_HALF (*(t+1)) + HIGH_HALF (*t)) / (cHigh + 1));
u = (NN_DIGIT)aLow * (NN_DIGIT)cLow;
v = (NN_DIGIT)aLow * (NN_DIGIT)cHigh;
if ((*t -= u) > (MAX_NN_DIGIT - u))
t[1]--;
if ((*t -= TO_HIGH_HALF (v)) > (MAX_NN_DIGIT - TO_HIGH_HALF (v)))
t[1]--;
*(t+1) -= HIGH_HALF (v);

while ((*(t+1) > 0) || ((*(t+1) == 0) && *t >= s)) {
if ((*t -= s) > (MAX_NN_DIGIT - s))
t[1]--;
aLow++;
}

ai = TO_HIGH_HALF (aHigh) + aLow;
s--;
}

cc[i+ddDigits] -= subdigitmult(&cc, &cc, ai, dd, ddDigits);

while (cc[i+ddDigits] || (NN_Cmp (&cc, dd, ddDigits) >= 0)) {
ai++;
cc[i+ddDigits] -= NN_Sub (&cc, &cc, dd, ddDigits);
}

a = ai;
}

NN_AssignZero (b, dDigits);
NN_RShift (b, cc, shift, ddDigits);
}


/* Computes a = b mod c.

Lengths: a[cDigits], b[bDigits], c[cDigits].
Assumes c > 0, bDigits < 2 * MAX_NN_DIGITS, cDigits < MAX_NN_DIGITS.
*/
void NN_Mod (a, b, bDigits, c, cDigits)
NN_DIGIT *a, *b, *c;
unsigned int bDigits, cDigits;
{
NN_DIGIT t[2 * MAX_NN_DIGITS];

NN_Div (t, a, b, bDigits, c, cDigits);
}

/* Computes a = b * c mod d.

Lengths: a[digits], b[digits], c[digits], d[digits].
Assumes d > 0, digits < MAX_NN_DIGITS.
*/
void NN_ModMult (a, b, c, d, digits)
NN_DIGIT *a, *b, *c, *d;
unsigned int digits;
{
NN_DIGIT t[2*MAX_NN_DIGITS];

NN_Mult (t, b, c, digits);
NN_Mod (a, t, 2 * digits, d, digits);
}

/* Computes a = b^c mod d.

Lengths: a[dDigits], b[dDigits], c[cDigits], d[dDigits].
Assumes d > 0, cDigits > 0, dDigits < MAX_NN_DIGITS.
*/
void NN_ModExp (a, b, c, cDigits, d, dDigits)
NN_DIGIT *a, *b, *c, *d;
unsigned int cDigits, dDigits;
{
NN_DIGIT bPower[3][MAX_NN_DIGITS], ci, t[MAX_NN_DIGITS];
int i;
unsigned int ciBits, j, s;

/* Store b, b^2 mod d, and b^3 mod d.
*/
NN_Assign (bPower[0], b, dDigits);
NN_ModMult (bPower[1], bPower[0], b, d, dDigits);
NN_ModMult (bPower[2], bPower[1], b, d, dDigits);

NN_ASSIGN_DIGIT (t, 1, dDigits);

cDigits = NN_Digits (c, cDigits);
for (i = cDigits - 1; i >= 0; i--) {
ci = c;
ciBits = NN_DIGIT_BITS;

/* Scan past leading zero bits of most significant digit.
*/
if (i == (int)(cDigits - 1)) {
while (! DIGIT_2MSB (ci)) {
ci <<= 2;
ciBits -= 2;
}
}

for (j = 0; j < ciBits; j += 2, ci <<= 2) {
/* Compute t = t^4 * b^s mod d, where s = two MSB's of ci. */
NN_ModMult (t, t, t, d, dDigits);
NN_ModMult (t, t, t, d, dDigits);
if ((s = DIGIT_2MSB (ci)) != 0)
NN_ModMult (t, t, bPower[s-1], d, dDigits);
}
}

NN_Assign (a, t, dDigits);
}

/* Compute a = 1/b mod c, assuming inverse exists.

Lengths: a[digits], b[digits], c[digits].
Assumes gcd (b, c) = 1, digits < MAX_NN_DIGITS.
*/
void NN_ModInv (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
NN_DIGIT q[MAX_NN_DIGITS], t1[MAX_NN_DIGITS], t3[MAX_NN_DIGITS],
u1[MAX_NN_DIGITS], u3[MAX_NN_DIGITS], v1[MAX_NN_DIGITS],
v3[MAX_NN_DIGITS], w[2*MAX_NN_DIGITS];
int u1Sign;

/* Apply extended Euclidean algorithm, modified to avoid negative
numbers.
*/
NN_ASSIGN_DIGIT (u1, 1, digits);
NN_AssignZero (v1, digits);
NN_Assign (u3, b, digits);
NN_Assign (v3, c, digits);
u1Sign = 1;

while (! NN_Zero (v3, digits)) {
NN_Div (q, t3, u3, digits, v3, digits);
NN_Mult (w, q, v1, digits);
NN_Add (t1, u1, w, digits);
NN_Assign (u1, v1, digits);
NN_Assign (v1, t1, digits);
NN_Assign (u3, v3, digits);
NN_Assign (v3, t3, digits);
u1Sign = -u1Sign;
}

/* Negate result if sign is negative. */
if (u1Sign < 0)
NN_Sub (a, c, u1, digits);
else
NN_Assign (a, u1, digits);
}

/* Computes a = gcd(b, c).

Assumes b > c, digits < MAX_NN_DIGITS.
*/

#define iplus1 ( i==2 ? 0 : i+1 ) /* used by Euclid algorithms */
#define iminus1 ( i==0 ? 2 : i-1 ) /* used by Euclid algorithms */
#define g(i) ( &(t[0]) )

void NN_Gcd(a ,b ,c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
short i;
NN_DIGIT t[3][MAX_NN_DIGITS];

NN_Assign(g(0), c, digits);
NN_Assign(g(1), b, digits);

i=1;

while(!NN_Zero(g(i),digits)) {
NN_Mod(g(iplus1), g(iminus1), digits, g(i), digits);
i = iplus1;
}

NN_Assign(a , g(iminus1), digits);
}

/* Returns the significant length of a in bits.

Lengths: a[digits]. */

unsigned int NN_Bits (a, digits)
NN_DIGIT *a;
unsigned int digits;
{
if ((digits = NN_Digits (a, digits)) == 0)
return (0);

return ((digits - 1) * NN_DIGIT_BITS + NN_DigitBits (a[digits-1]));
}

#ifndef USEASM

/* Returns sign of a - b. */

int NN_Cmp (a, b, digits)
NN_DIGIT *a, *b;
unsigned int digits;
{

if(digits) {
do {
digits--;
if(*(a+digits) > *(b+digits))
return(1);
if(*(a+digits) < *(b+digits))
return(-1);
}while(digits);
}

return (0);
}

/* Returns nonzero iff a is zero. */

int NN_Zero (a, digits)
NN_DIGIT *a;
unsigned int digits;
{
if(digits) {
do {
if(*a++)
return(0);
}while(--digits);
}

return (1);
}

/* Assigns a = b. */

void NN_Assign (a, b, digits)
NN_DIGIT *a, *b;
unsigned int digits;
{
if(digits) {
do {
*a++ = *b++;
}while(--digits);
}
}

/* Returns the significant length of a in digits. */

unsigned int NN_Digits (a, digits)
NN_DIGIT *a;
unsigned int digits;
{

if(digits) {
digits--;

do {
if(*(a+digits))
break;
}while(digits--);

return(digits + 1);
}

return(digits);
}

/* Computes a = b + c. Returns carry.

Lengths: a[digits], b[digits], c[digits].
*/
NN_DIGIT NN_Add (a, b, c, digits)
NN_DIGIT *a, *b, *c;
unsigned int digits;
{
NN_DIGIT temp, carry = 0;

if(digits)
do {
if((temp = (*b++) + carry) < carry)
temp = *c++;
else
if((temp += *c) < *c++)
carry = 1;
else
carry = 0;
*a++ = temp;
}while(--digits);

return (carry);
}

#endif

static NN_DIGIT subdigitmult(a, b, c, d, digits)
NN_DIGIT *a, *b, c, *d;
unsigned int digits;
{
NN_DIGIT borrow, thigh, tlow;
unsigned int i;

borrow = 0;

if(c != 0) {
for(i = 0; i < digits; i++) {
dmult(c, d, &thigh, &tlow);
if((a = b - borrow) > (MAX_NN_DIGIT - borrow))
borrow = 1;
else
borrow = 0;
if((a -= tlow) > (MAX_NN_DIGIT - tlow))
borrow++;
borrow += thigh;
}
}

return (borrow);
}

/* Returns the significant length of a in bits, where a is a digit. */

static unsigned int NN_DigitBits (a)
NN_DIGIT a;
{
unsigned int i;

for (i = 0; i < NN_DIGIT_BITS; i++, a >>= 1)
if (a == 0)
break;

return (i);
}

/* Computes a * b, result stored in high and low. */

static void dmult( a, b, high, low)
NN_DIGIT a, b;
NN_DIGIT *high;
NN_DIGIT *low;
{
NN_HALF_DIGIT al, ah, bl, bh;
NN_DIGIT m1, m2, m, ml, mh, carry = 0;

al = (NN_HALF_DIGIT)LOW_HALF(a);
ah = (NN_HALF_DIGIT)HIGH_HALF(a);
bl = (NN_HALF_DIGIT)LOW_HALF(b);
bh = (NN_HALF_DIGIT)HIGH_HALF(b);

*low = (NN_DIGIT) al*bl;
*high = (NN_DIGIT) ah*bh;

m1 = (NN_DIGIT) al*bh;
m2 = (NN_DIGIT) ah*bl;
m = m1 + m2;

if(m < m1)
carry = 1L << (NN_DIGIT_BITS / 2);

ml = (m & MAX_NN_HALF_DIGIT) << (NN_DIGIT_BITS / 2);
mh = m >> (NN_DIGIT_BITS / 2);

*low += ml;

if(*low < ml)
carry++;

*high += carry + mh;
}

/*
NN.H - header file for NN.C

Copyright (c) J.S.A.Kapp 1994 - 1995.

RSAEURO - RSA Library compatible with RSAREF(tm) 2.0.

All functions prototypes are the Same as for RSAREF(tm).
To aid compatiblity the source and the files follow the
same naming comventions that RSAREF(tm) uses. This should aid
direct importing to your applications.

This library is legal everywhere outside the US. And should
NOT be imported to the US and used there.

All Trademarks Acknowledged.

Math Library Routines Header File.

Revision 1.00 - JSAK 23/6/95, Final Release Version
*/

#ifndef _NN_H_
#define _NN_H_

#ifdef __cplusplus
extern "C" {
#endif

/* Type definitions. */

typedef UINT4 NN_DIGIT;
typedef UINT2 NN_HALF_DIGIT;

/* Constants.

Note: MAX_NN_DIGITS is long enough to hold any RSA modulus, plus
one more digit as required by R_GeneratePEMKeys (for n and phiN,
whose lengths must be even). All natural numbers have at most
MAX_NN_DIGITS digits, except for double-length intermediate values
in NN_Mult (t), NN_ModMult (t), NN_ModInv (w), and NN_Div (c).
*/

/* Length of digit in bits */
#define NN_DIGIT_BITS 32
#define NN_HALF_DIGIT_BITS 16
/* Length of digit in bytes */
#define NN_DIGIT_LEN (NN_DIGIT_BITS / 8)
/* Maximum length in digits */
#define MAX_NN_DIGITS /
((MAX_RSA_MODULUS_LEN + NN_DIGIT_LEN - 1) / NN_DIGIT_LEN + 1)
/* Maximum digits */
#define MAX_NN_DIGIT 0xffffffff
#define MAX_NN_HALF_DIGIT 0xffff

#define NN_LT -1
#define NN_EQ 0
#define NN_GT 1

/* Macros. */

#define LOW_HALF(x) ((x) & MAX_NN_HALF_DIGIT)
#define HIGH_HALF(x) (((x) >> NN_HALF_DIGIT_BITS) & MAX_NN_HALF_DIGIT)
#define TO_HIGH_HALF(x) (((NN_DIGIT)(x)) << NN_HALF_DIGIT_BITS)
#define DIGIT_MSB(x) (unsigned int)(((x) >> (NN_DIGIT_BITS - 1)) & 1)
#define DIGIT_2MSB(x) (unsigned int)(((x) >> (NN_DIGIT_BITS - 2)) & 3)

/* CONVERSIONS
NN_Decode (a, digits, b, len) Decodes character string b into a.
NN_Encode (a, len, b, digits) Encodes a into character string b.

ASSIGNMENTS
NN_Assign (a, b, digits) Assigns a = b.
NN_ASSIGN_DIGIT (a, b, digits) Assigns a = b, where b is a digit.
NN_AssignZero (a, b, digits) Assigns a = 0.
NN_Assign2Exp (a, b, digits) Assigns a = 2^b.

ARITHMETIC OPERATIONS
NN_Add (a, b, c, digits) Computes a = b + c.
NN_Sub (a, b, c, digits) Computes a = b - c.
NN_Mult (a, b, c, digits) Computes a = b * c.
NN_LShift (a, b, c, digits) Computes a = b * 2^c.
NN_RShift (a, b, c, digits) Computes a = b / 2^c.
NN_Div (a, b, c, cDigits, d, dDigits) Computes a = c div d and b = c mod d.

NUMBER THEORY
NN_Mod (a, b, bDigits, c, cDigits) Computes a = b mod c.
NN_ModMult (a, b, c, d, digits) Computes a = b * c mod d.
NN_ModExp (a, b, c, cDigits, d, dDigits) Computes a = b^c mod d.
NN_ModInv (a, b, c, digits) Computes a = 1/b mod c.
NN_Gcd (a, b, c, digits) Computes a = gcd (b, c).

OTHER OPERATIONS
NN_EVEN (a, digits) Returns 1 iff a is even.
NN_Cmp (a, b, digits) Returns sign of a - b.
NN_EQUAL (a, digits) Returns 1 iff a = b.
NN_Zero (a, digits) Returns 1 iff a = 0.
NN_Digits (a, digits) Returns significant length of a in digits.
NN_Bits (a, digits) Returns significant length of a in bits.
*/
void NN_Decode PROTO_LIST
((NN_DIGIT *, unsigned int, unsigned char *, unsigned int));
void NN_Encode PROTO_LIST
((unsigned char *, unsigned int, NN_DIGIT *, unsigned int));

void NN_Assign PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, unsigned int));
void NN_AssignZero PROTO_LIST ((NN_DIGIT *, unsigned int));
void NN_Assign2Exp PROTO_LIST ((NN_DIGIT *, unsigned int, unsigned int));

NN_DIGIT NN_Add PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int));
NN_DIGIT NN_Sub PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int));
void NN_Mult PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int));
void NN_Div PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *,
unsigned int));
NN_DIGIT NN_LShift PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));
NN_DIGIT NN_RShift PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));
NN_DIGIT NN_LRotate PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, unsigned int, unsigned int));

void NN_Mod PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *, unsigned int));
void NN_ModMult PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int));
void NN_ModExp PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int, NN_DIGIT *,
unsigned int));
void NN_ModInv PROTO_LIST
((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int));
void NN_Gcd PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, NN_DIGIT *, unsigned int));

int NN_Cmp PROTO_LIST ((NN_DIGIT *, NN_DIGIT *, unsigned int));
int NN_Zero PROTO_LIST ((NN_DIGIT *, unsigned int));
unsigned int NN_Bits PROTO_LIST ((NN_DIGIT *, unsigned int));
unsigned int NN_Digits PROTO_LIST ((NN_DIGIT *, unsigned int));

#define NN_ASSIGN_DIGIT(a, b, digits) {NN_AssignZero (a, digits); a[0] = b;}
#define NN_EQUAL(a, b, digits) (! NN_Cmp (a, b, digits))
#define NN_EVEN(a, digits) (((digits) == 0) || ! (a[0] & 1))

#ifdef __cplusplus
}
#endif

#endif /* _NN_H_ */

第一部分
{License, info, etc
------------------

This implementation is made by Walied Othman, to contact me
mail to Walied.Othman@Student.KULeuven.ac.be or
Triade@ace.Ulyssis.Student.KULeuven.ac.be,
always mention wether it 's about the FGInt for Delphi or for
FreePascal, or wether it 's about the 6xs, preferably in the subject line.
If you 're going to use these implementations, at least mention my
name or something and notify me so I may even put a link on my page.
This implementation is freeware and according to the coderpunks'
manifesto it should remain so, so don 't use these implementations
in commercial software. Encryption, as a tool to ensure privacy
should be free and accessible for anyone. If you plan to use these
implementations in a commercial application, contact me before
doing so, that way you can license the software to use it in commercial
Software. If any algorithm is patented in your country, you should
acquire a license before using this software. Modified versions of this
software must contain an acknowledgement of the original author (=me).
This implementaion is available at
http://ace.ulyssis.student.kuleuven.ac.be/~triade/

copyright 2000, Walied Othman
This header may not be removed.
}

Unit FGInt;

Interface

Uses Windows, SysUtils, Controls, Math;

Type
TCompare = (Lt, St, Eq, Er);
TSign = (negative, positive);
TFGInt = Record
Sign : TSign;
Number : Array Of int64;
End;

Procedure zeronetochar8(Var g : char; Const x : String);
Procedure zeronetochar6(Var g : integer; Const x : String);
Procedure initialize8(Var trans : Array Of String);
Procedure initialize6(Var trans : Array Of String);
Procedure initialize6PGP(Var trans : Array Of String);
Procedure ConvertBase256to64(Const str256 : String; Var str64 : String);
Procedure ConvertBase64to256(Const str64 : String; Var str256 : String);
Procedure ConvertBase256to2(Const str256 : String; Var str2 : String);
Procedure ConvertBase64to2(Const str64 : String; Var str2 : String);
Procedure ConvertBase2to256(str2 : String; Var str256 : String);
Procedure ConvertBase2to64(str2 : String; Var str64 : String);
Procedure ConvertBase256StringToHexString(Str256 : String; Var HexStr : String);
Procedure ConvertHexStringToBase256String(HexStr : String; Var Str256 : String);
Procedure PGPConvertBase256to64(Var str256, str64 : String);
Procedure PGPConvertBase64to256(str64 : String; Var str256 : String);
Procedure PGPConvertBase64to2(str64 : String; Var str2 : String);
Procedure Base10StringToFGInt(Base10 : String; Var FGInt : TFGInt);
Procedure FGIntToBase10String(Const FGInt : TFGInt; Var Base10 : String);
Procedure FGIntDestroy(Var FGInt : TFGInt);
Function FGIntCompareAbs(Const FGInt1, FGInt2 : TFGInt) : TCompare;
Procedure FGIntAdd(Const FGInt1, FGInt2 : TFGInt; Var Sum : TFGInt);
Procedure FGIntChangeSign(Var FGInt : TFGInt);
Procedure FGIntSub(Var FGInt1, FGInt2, dif : TFGInt);
Procedure FGIntMulByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64);
Procedure FGIntMulByIntbis(Var FGInt : TFGInt; by : int64);
Procedure FGIntDivByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64; Var modres : int64);
Procedure FGIntDivByIntBis(Var FGInt : TFGInt; by : int64; Var modres : int64);
Procedure FGIntModByInt(Const FGInt : TFGInt; by : int64; Var modres : int64);
Procedure FGIntAbs(Var FGInt : TFGInt);
Procedure FGIntCopy(Const FGInt1 : TFGInt; Var FGInt2 : TFGInt);
Procedure FGIntShiftLeft(Var FGInt : TFGInt);
Procedure FGIntShiftRight(Var FGInt : TFGInt);
Procedure FGIntShiftRightBy31(Var FGInt : TFGInt);
Procedure FGIntAddBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt);
Procedure FGIntSubBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt);
Procedure FGIntMul(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt);
Procedure FGIntSquare(Const FGInt : TFGInt; Var Square : TFGInt);
Procedure FGIntToBase2String(Const FGInt : TFGInt; Var S : String);
Procedure Base2StringToFGInt(S : String; Var FGInt : TFGInt);
Procedure FGIntToBase256String(Const FGInt : TFGInt; Var str256 : String);
Procedure Base256StringToFGInt(str256 : String; Var FGInt : TFGInt);
Procedure PGPMPIToFGInt(PGPMPI : String; Var FGInt : TFGInt);
Procedure FGIntToPGPMPI(FGInt : TFGInt; Var PGPMPI : String);
Procedure FGIntExp(Const FGInt, exp : TFGInt; Var res : TFGInt);
Procedure FGIntFac(Const FGInt : TFGInt; Var res : TFGInt);
Procedure FGIntShiftLeftBy31(Var FGInt : TFGInt);
Procedure FGIntDivMod(Var FGInt1, FGInt2, QFGInt, MFGInt : TFGInt);
Procedure FGIntDiv(Var FGInt1, FGInt2, QFGInt : TFGInt);
Procedure FGIntMod(Var FGInt1, FGInt2, MFGInt : TFGInt);
Procedure FGIntSquareMod(Var FGInt, Modb, FGIntSM : TFGInt);
Procedure FGIntAddMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt);
Procedure FGIntMulMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt);
Procedure FGIntModExp(Var FGInt, exp, modb, res : TFGInt);
Procedure FGIntModBis(Const FGInt : TFGInt; Var FGIntOut : TFGInt; b : longint; head : int64);
Procedure FGIntMulModBis(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt; b : longint; head : int64);
Procedure FGIntMontgomeryMod(Const GInt, base, baseInv : TFGInt; Var MGInt : TFGInt; b : longint; head : int64);
Procedure FGIntMontgomeryModExp(Var FGInt, exp, modb, res : TFGInt);
Procedure FGIntGCD(Const FGInt1, FGInt2 : TFGInt; Var GCD : TFGInt);
Procedure FGIntLCM(Const FGInt1, FGInt2 : TFGInt; Var LCM : TFGInt);
Procedure FGIntTrialDiv9999(Const FGInt : TFGInt; Var ok : boolean);
Procedure FGIntRandom1(Var Seed, RandomFGInt : TFGInt);
Procedure FGIntRabinMiller(Var FGIntp : TFGInt; nrtest : integer; Var ok : boolean);
Procedure FGIntBezoutBachet(Var FGInt1, FGInt2, a, b : TFGInt);
Procedure FGIntModInv(Const FGInt1, base : TFGInt; Var Inverse : TFGInt);
Procedure FGIntPrimetest(Var FGIntp : TFGInt; nrRMtests : integer; Var ok : boolean);
Procedure FGIntLegendreSymbol(Var a, p : TFGInt; Var L : integer);
Procedure FGIntSquareRootModP(Square, Prime : TFGInt; Var SquareRoot : TFGInt);



Implementation

Var
primes : Array[1..1228] Of integer =
(3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251,
257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389,
397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677,
683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839,
853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009,
1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123,
1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279,
1283, 1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429,
1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553,
1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693,
1697, 1699, 1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847,
1861, 1867, 1871, 1873, 1877, 1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997,
1999, 2003, 2011, 2017, 2027, 2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131,
2137, 2141, 2143, 2153, 2161, 2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287,
2293, 2297, 2309, 2311, 2333, 2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417,
2423, 2437, 2441, 2447, 2459, 2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593,
2609, 2617, 2621, 2633, 2647, 2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719,
2729, 2731, 2741, 2749, 2753, 2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861,
2879, 2887, 2897, 2903, 2909, 2917, 2927, 2939, 2953, 2957, 2963, 2969, 2971, 2999, 3001, 3011, 3019, 3023, 3037,
3041, 3049, 3061, 3067, 3079, 3083, 3089, 3109, 3119, 3121, 3137, 3163, 3167, 3169, 3181, 3187, 3191, 3203, 3209,
3217, 3221, 3229, 3251, 3253, 3257, 3259, 3271, 3299, 3301, 3307, 3313, 3319, 3323, 3329, 3331, 3343, 3347, 3359,
3361, 3371, 3373, 3389, 3391, 3407, 3413, 3433, 3449, 3457, 3461, 3463, 3467, 3469, 3491, 3499, 3511, 3517, 3527,
3529, 3533, 3539, 3541, 3547, 3557, 3559, 3571, 3581, 3583, 3593, 3607, 3613, 3617, 3623, 3631, 3637, 3643, 3659,
3671, 3673, 3677, 3691, 3697, 3701, 3709, 3719, 3727, 3733, 3739, 3761, 3767, 3769, 3779, 3793, 3797, 3803, 3821,
3823, 3833, 3847, 3851, 3853, 3863, 3877, 3881, 3889, 3907, 3911, 3917, 3919, 3923, 3929, 3931, 3943, 3947, 3967,
3989, 4001, 4003, 4007, 4013, 4019, 4021, 4027, 4049, 4051, 4057, 4073, 4079, 4091, 4093, 4099, 4111, 4127, 4129,
4133, 4139, 4153, 4157, 4159, 4177, 4201, 4211, 4217, 4219, 4229, 4231, 4241, 4243, 4253, 4259, 4261, 4271, 4273,
4283, 4289, 4297, 4327, 4337, 4339, 4349, 4357, 4363, 4373, 4391, 4397, 4409, 4421, 4423, 4441, 4447, 4451, 4457,
4463, 4481, 4483, 4493, 4507, 4513, 4517, 4519, 4523, 4547, 4549, 4561, 4567, 4583, 4591, 4597, 4603, 4621, 4637,
4639, 4643, 4649, 4651, 4657, 4663, 4673, 4679, 4691, 4703, 4721, 4723, 4729, 4733, 4751, 4759, 4783, 4787, 4789,
4793, 4799, 4801, 4813, 4817, 4831, 4861, 4871, 4877, 4889, 4903, 4909, 4919, 4931, 4933, 4937, 4943, 4951, 4957,
4967, 4969, 4973, 4987, 4993, 4999, 5003, 5009, 5011, 5021, 5023, 5039, 5051, 5059, 5077, 5081, 5087, 5099, 5101,
5107, 5113, 5119, 5147, 5153, 5167, 5171, 5179, 5189, 5197, 5209, 5227, 5231, 5233, 5237, 5261, 5273, 5279, 5281,
5297, 5303, 5309, 5323, 5333, 5347, 5351, 5381, 5387, 5393, 5399, 5407, 5413, 5417, 5419, 5431, 5437, 5441, 5443,
5449, 5471, 5477, 5479, 5483, 5501, 5503, 5507, 5519, 5521, 5527, 5531, 5557, 5563, 5569, 5573, 5581, 5591, 5623,
5639, 5641, 5647, 5651, 5653, 5657, 5659, 5669, 5683, 5689, 5693, 5701, 5711, 5717, 5737, 5741, 5743, 5749, 5779,
5783, 5791, 5801, 5807, 5813, 5821, 5827, 5839, 5843, 5849, 5851, 5857, 5861, 5867, 5869, 5879, 5881, 5897, 5903,
5923, 5927, 5939, 5953, 5981, 5987, 6007, 6011, 6029, 6037, 6043, 6047, 6053, 6067, 6073, 6079, 6089, 6091, 6101,
6113, 6121, 6131, 6133, 6143, 6151, 6163, 6173, 6197, 6199, 6203, 6211, 6217, 6221, 6229, 6247, 6257, 6263, 6269,
6271, 6277, 6287, 6299, 6301, 6311, 6317, 6323, 6329, 6337, 6343, 6353, 6359, 6361, 6367, 6373, 6379, 6389, 6397,
6421, 6427, 6449, 6451, 6469, 6473, 6481, 6491, 6521, 6529, 6547, 6551, 6553, 6563, 6569, 6571, 6577, 6581, 6599,
6607, 6619, 6637, 6653, 6659, 6661, 6673, 6679, 6689, 6691, 6701, 6703, 6709, 6719, 6733, 6737, 6761, 6763, 6779,
6781, 6791, 6793, 6803, 6823, 6827, 6829, 6833, 6841, 6857, 6863, 6869, 6871, 6883, 6899, 6907, 6911, 6917, 6947,
6949, 6959, 6961, 6967, 6971, 6977, 6983, 6991, 6997, 7001, 7013, 7019, 7027, 7039, 7043, 7057, 7069, 7079, 7103,
7109, 7121, 7127, 7129, 7151, 7159, 7177, 7187, 7193, 7207, 7211, 7213, 7219, 7229, 7237, 7243, 7247, 7253, 7283,
7297, 7307, 7309, 7321, 7331, 7333, 7349, 7351, 7369, 7393, 7411, 7417, 7433, 7451, 7457, 7459, 7477, 7481, 7487,
7489, 7499, 7507, 7517, 7523, 7529, 7537, 7541, 7547, 7549, 7559, 7561, 7573, 7577, 7583, 7589, 7591, 7603, 7607,
7621, 7639, 7643, 7649, 7669, 7673, 7681, 7687, 7691, 7699, 7703, 7717, 7723, 7727, 7741, 7753, 7757, 7759, 7789,
7793, 7817, 7823, 7829, 7841, 7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 7927, 7933, 7937, 7949, 7951,
7963, 7993, 8009, 8011, 8017, 8039, 8053, 8059, 8069, 8081, 8087, 8089, 8093, 8101, 8111, 8117, 8123, 8147, 8161,
8167, 8171, 8179, 8191, 8209, 8219, 8221, 8231, 8233, 8237, 8243, 8263, 8269, 8273, 8287, 8291, 8293, 8297, 8311,
8317, 8329, 8353, 8363, 8369, 8377, 8387, 8389, 8419, 8423, 8429, 8431, 8443, 8447, 8461, 8467, 8501, 8513, 8521,
8527, 8537, 8539, 8543, 8563, 8573, 8581, 8597, 8599, 8609, 8623, 8627, 8629, 8641, 8647, 8663, 8669, 8677, 8681,
8689, 8693, 8699, 8707, 8713, 8719, 8731, 8737, 8741, 8747, 8753, 8761, 8779, 8783, 8803, 8807, 8819, 8821, 8831,
8837, 8839, 8849, 8861, 8863, 8867, 8887, 8893, 8923, 8929, 8933, 8941, 8951, 8963, 8969, 8971, 8999, 9001, 9007,
9011, 9013, 9029, 9041, 9043, 9049, 9059, 9067, 9091, 9103, 9109, 9127, 9133, 9137, 9151, 9157, 9161, 9173, 9181,
9187, 9199, 9203, 9209, 9221, 9227, 9239, 9241, 9257, 9277, 9281, 9283, 9293, 9311, 9319, 9323, 9337, 9341, 9343,
9349, 9371, 9377, 9391, 9397, 9403, 9413, 9419, 9421, 9431, 9433, 9437, 9439, 9461, 9463, 9467, 9473, 9479, 9491,
9497, 9511, 9521, 9533, 9539, 9547, 9551, 9587, 9601, 9613, 9619, 9623, 9629, 9631, 9643, 9649, 9661, 9677, 9679,
9689, 9697, 9719, 9721, 9733, 9739, 9743, 9749, 9767, 9769, 9781, 9787, 9791, 9803, 9811, 9817, 9829, 9833, 9839,
9851, 9857, 9859, 9871, 9883, 9887, 9901, 9907, 9923, 9929, 9931, 9941, 9949, 9967, 9973);
chr64 : Array[1..64] Of char = ('a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F',
'g', 'G', 'h', 'H', 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p',
'P', 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X', 'y', 'Y',
'z', 'Z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '=');
PGPchr64 : Array[1..64] Of char = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', 'a', 'b', 'c', 'd', 'e', 'f',
'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
'z', '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '+', '/');


{$H+}


Procedure zeronetochar8(Var g : char; Const x : String);
Var
i : Integer;
b : byte;
Begin
b := 0;
For i := 1 To 8 Do
Begin
If copy(x, i, 1) = '1' Then
b := b Or (1 Shl (8 - I));
End;
g := chr(b);
End;


Procedure zeronetochar6(Var g : integer; Const x : String);
Var
I : Integer;
Begin
G := 0;
For I := 1 To Length(X) Do
Begin
If I > 6 Then
Break;
If X <> '0' Then
G := G Or (1 Shl (6 - I));
End;
Inc(G);
End;


Procedure initialize8(Var trans : Array Of String);
Var
c1, c2, c3, c4, c5, c6, c7, c8 : integer;
x : String;
g : char;
Begin
For c1 := 0 To 1 Do
For c2 := 0 To 1 Do
For c3 := 0 To 1 Do
For c4 := 0 To 1 Do
For c5 := 0 To 1 Do
For c6 := 0 To 1 Do
For c7 := 0 To 1 Do
For c8 := 0 To 1 Do
Begin
x := '';
x := inttostr(c1) + inttostr(c2) + inttostr(c3) + inttostr(c4) + inttostr(c5) + inttostr(c6) + inttostr(c7) + inttostr(c8);
zeronetochar8(g, x);
trans[ord(g)] := x;
End;
End;


Procedure initialize6(Var trans : Array Of String);
Var
c1, c2, c3, c4, c5, c6 : integer;
x : String;
g : integer;
Begin
For c1 := 0 To 1 Do
For c2 := 0 To 1 Do
For c3 := 0 To 1 Do
For c4 := 0 To 1 Do
For c5 := 0 To 1 Do
For c6 := 0 To 1 Do
Begin
x := '';
x := inttostr(c1) + inttostr(c2) + inttostr(c3) + inttostr(c4) + inttostr(c5) + inttostr(c6);
zeronetochar6(g, x);
trans[ord(chr64[g])] := x;
End;
End;

Procedure initialize6PGP(Var trans : Array Of String);
Var
c1, c2, c3, c4, c5, c6 : integer;
x : String;
g : integer;
Begin
For c1 := 0 To 1 Do
For c2 := 0 To 1 Do
For c3 := 0 To 1 Do
For c4 := 0 To 1 Do
For c5 := 0 To 1 Do
For c6 := 0 To 1 Do
Begin
x := '';
x := inttostr(c1) + inttostr(c2) + inttostr(c3) + inttostr(c4) + inttostr(c5) + inttostr(c6);
zeronetochar6(g, x);
trans[ord(PGPchr64[g])] := x;
End;
End;


// Convert base 8 strings to base 6 strings and visa versa

Procedure ConvertBase256to64(Const str256 : String; Var str64 : String);
Var
temp : String;
trans : Array[0..255] Of String;
i, len6 : longint;
g : integer;
Begin
initialize8(trans);
temp := '';
For i := 1 To length(str256) Do temp := temp + trans[ord(str256)];
While (length(temp) Mod 6) <> 0 Do temp := temp + '0';
len6 := length(temp) Div 6;
str64 := '';
For i := 1 To len6 Do
Begin
zeronetochar6(g, copy(temp, 1, 6));
str64 := str64 + chr64[g];
delete(temp, 1, 6);
End;
End;


Procedure ConvertBase64to256(Const str64 : String; Var str256 : String);
Var
temp : String;
trans : Array[0..255] Of String;
i, len8 : longint;
g : char;
Begin
initialize6(trans);
temp := '';
For i := 1 To length(str64) Do temp := temp + trans[ord(str64)];
str256 := '';
len8 := length(temp) Div 8;
For i := 1 To len8 Do
Begin
zeronetochar8(g, copy(temp, 1, 8));
str256 := str256 + g;
delete(temp, 1, 8);
End;
End;


// Convert base 8 & 6 bit strings to base 2 strings and visa versa

Procedure ConvertBase256to2(Const str256 : String; Var str2 : String);
Var
trans : Array[0..255] Of String;
i : longint;
Begin
str2 := '';
initialize8(trans);
For i := 1 To length(str256) Do str2 := str2 + trans[ord(str256)];
End;


Procedure ConvertBase64to2(Const str64 : String; Var str2 : String);
Var
trans : Array[0..255] Of String;
i : longint;
Begin
str2 := '';
initialize6(trans);
For i := 1 To length(str64) Do str2 := str2 + trans[ord(str64)];
End;


Procedure ConvertBase2to256(str2 : String; Var str256 : String);
Var
i, len8 : longint;
g : char;
Begin
str256 := '';
While (length(str2) Mod 8) <> 0 Do str2 := '0' + str2;
len8 := length(str2) Div 8;
For i := 1 To len8 Do
Begin
zeronetochar8(g, copy(str2, 1, 8));
str256 := str256 + g;
delete(str2, 1, 8);
End;
End;


Procedure ConvertBase2to64(str2 : String; Var str64 : String);
Var
i, len6 : longint;
g : integer;
Begin
str64 := '';
While (length(str2) Mod 6) <> 0 Do str2 := '0' + str2;
len6 := length(str2) Div 6;
For i := 1 To len6 Do
Begin
zeronetochar6(g, copy(str2, 1, 6));
str64 := str64 + chr64[g];
delete(str2, 1, 6);
End;
End;


// Convert base 256 strings to base 16 (HexaDecimal) strings and visa versa

Procedure ConvertBase256StringToHexString(Str256 : String; Var HexStr : String);
Var
i : longint;
b : byte;
Begin
HexStr := '';
For i := 1 To length(str256) Do
Begin
b := ord(str256);
If (b Shr 4) < 10 Then HexStr := HexStr + chr(48 + (b Shr 4))
Else HexStr := HexStr + chr(55 + (b Shr 4));
If (b And 15) < 10 Then HexStr := HexStr + chr(48 + (b And 15))
Else HexStr := HexStr + chr(55 + (b And 15));
End;
End;


Procedure ConvertHexStringToBase256String(HexStr : String; Var Str256 : String);
Var
i : longint;
b, h1, h2 : byte;
Begin
Str256 := '';
For i := 1 To (length(Hexstr) Div 2) Do
Begin
h2 := ord(HexStr[2 * i]);
h1 := ord(HexStr[2 * i - 1]);
If h1 < 58 Then b := ((h1 - 48) Shl 4) Else b := ((h1 - 55) Shl 4);
If h2 < 58 Then b := (b Or (h2 - 48)) Else b := (b Or (h2 - 55));
Str256 := Str256 + chr(b);
End;
End;


// Convert base 256 strings to base 64 strings and visa versa, PGP style

Procedure PGPConvertBase256to64(Var str256, str64 : String);
Var
temp, x, a : String;
i, len6 : longint;
g : integer;
trans : Array[0..255] Of String;
Begin
initialize8(trans);
temp := '';
For i := 1 To length(str256) Do temp := temp + trans[ord(str256)];
If (length(temp) Mod 6) = 0 Then a := '' Else
If (length(temp) Mod 6) = 4 Then
Begin
temp := temp + '00';
a := '='
End
Else
Begin
temp := temp + '0000';
a := '=='
End;
str64 := '';
len6 := length(temp) Div 6;
For i := 1 To len6 Do
Begin
x := copy(temp, 1, 6);
zeronetochar6(g, x);
str64 := str64 + PGPchr64[g];
delete(temp, 1, 6);
End;
str64 := str64 + a;
End;


Procedure PGPConvertBase64to256(str64 : String; Var str256 : String);
Var
temp, x : String;
i, j, len8 : longint;
g : char;
trans : Array[0..255] Of String;
Begin
initialize6PGP(trans);
temp := '';
str256 := '';
If str64[length(str64) - 1] = '=' Then j := 2 Else
If str64[length(str64)] = '=' Then j := 1 Else j := 0;
For i := 1 To (length(str64) - j) Do temp := temp + trans[ord(str64)];
If j <> 0 Then delete(temp, length(temp) - 2 * j + 1, 2 * j);
len8 := length(temp) Div 8;
For i := 1 To len8 Do
Begin
x := copy(temp, 1, 8);
zeronetochar8(g, x);
str256 := str256 + g;
delete(temp, 1, 8);
End;
End;

// Convert base 64 strings to base 2 strings, PGP style


Procedure PGPConvertBase64to2(str64 : String; Var str2 : String);
Var
i, j : longint;
trans : Array[0..255] Of String;
Begin
str2 := '';
initialize6(trans);
If str64[length(str64) - 1] = '=' Then j := 2 Else
If str64[length(str64)] = '=' Then j := 1 Else j := 0;
For i := 1 To (length(str64) - j) Do str2 := str2 + trans[ord(str64)];
delete(str2, length(str2) - 2 * j + 1, 2 * j);
End;


// Convert a base 10 string to a FGInt

Procedure Base10StringToFGInt(Base10 : String; Var FGInt : TFGInt);
Var
i, size : longint;
j : int64;
S : String;
sign : TSign;

Procedure GIntDivByIntBis1(Var GInt : TFGInt; by : int64; Var modres : int64);
Var
i, size : longint;
rest : int64;
Begin
size := GInt.Number[0];
modres := 0;
For i := size Downto 1 Do
Begin
modres := modres * 1000000000;
rest := modres + GInt.Number;
GInt.Number := rest Div by;
modres := rest Mod by;
End;
While (GInt.Number[size] = 0) And (size > 1) Do size := size - 1;
If size <> GInt.Number[0] Then
Begin
SetLength(GInt.Number, size + 1);
GInt.Number[0] := size;
End;
End;

Begin
While (Not (Base10[1] In ['-', '0'..'9'])) And (length(Base10) > 1) Do
delete(Base10, 1, 1);
If copy(Base10, 1, 1) = '-' Then
Begin
Sign := negative;
delete(Base10, 1, 1);
End
Else Sign := positive;
While (length(Base10) > 1) And (copy(Base10, 1, 1) = '0') Do delete(Base10, 1, 1);
size := length(Base10) Div 9;
If (length(Base10) Mod 9) <> 0 Then size := size + 1;
SetLength(FGInt.Number, size + 1);
FGInt.Number[0] := size;
For i := 1 To size - 1 Do
Begin
FGInt.Number := StrToInt(copy(Base10, length(Base10) - 8, 9));
delete(Base10, length(Base10) - 8, 9);
End;
FGInt.Number[size] := StrToInt(Base10);

S := '';
While (FGInt.Number[0] <> 1) Or (FGInt.Number[1] <> 0) Do
Begin
GIntDivByIntBis1(FGInt, 2, j);
S := inttostr(j) + S;
End;
S := '0' + S;
FGIntDestroy(FGInt);
Base2StringToFGInt(S, FGInt);
FGInt.Sign := sign;
End;


// Convert a FGInt to a base 10 string

Procedure FGIntToBase10String(Const FGInt : TFGInt; Var Base10 : String);
Var
S : String;
j : int64;
temp : TFGInt;
Begin
FGIntCopy(FGInt, temp);
Base10 := '';
While (temp.Number[0] > 1) Or (temp.Number[1] > 0) Do
Begin
FGIntDivByIntBis(temp, 1000000000, j);
S := IntToStr(j);
While Length(S) < 9 Do S := '0' + S;
Base10 := S + Base10;
End;
Base10 := '0' + Base10;
While (length(Base10) > 1) And (Base10[1] = '0') Do delete(Base10, 1, 1);
If FGInt.Sign = negative Then Base10 := '-' + Base10;
End;



// Destroy a FGInt to free memory

Procedure FGIntDestroy(Var FGInt : TFGInt);
Begin
FGInt.Number := Nil;
End;


// Compare 2 FGInts in absolute value, returns
// Lt if FGInt1 > FGInt2, St if FGInt1 < FGInt2, Eq if FGInt1 = FGInt2,
// Er otherwise

Function FGIntCompareAbs(Const FGInt1, FGInt2 : TFGInt) : TCompare;
Var
size1, size2, i : longint;
Begin
FGIntCompareAbs := Er;
size1 := FGInt1.Number[0];
size2 := FGInt2.Number[0];
If size1 > size2 Then FGIntCompareAbs := Lt Else
If size1 < size2 Then FGIntCompareAbs := St Else
Begin
i := size2;
While (FGInt1.Number = FGInt2.Number) And (i > 1) Do i := i - 1;
If FGInt1.Number = FGInt2.Number Then FGIntCompareAbs := Eq Else
If FGInt1.Number < FGInt2.Number Then FGIntCompareAbs := St Else
If FGInt1.Number > FGInt2.Number Then FGIntCompareAbs := Lt;
End;
End;


// Add 2 FGInts, FGInt1 + FGInt2 = Sum

Procedure FGIntAdd(Const FGInt1, FGInt2 : TFGInt; Var Sum : TFGInt);
Var
i, size1, size2, size : longint;
rest : integer;
Trest : int64;
Begin
size1 := FGInt1.Number[0];
size2 := FGInt2.Number[0];
If size1 < size2 Then FGIntAdd(FGInt2, FGInt1, Sum) Else
Begin
If FGInt1.Sign = FGInt2.Sign Then
Begin
Sum.Sign := FGInt1.Sign;
SetLength(Sum.Number, size1 + 2);
rest := 0;
For i := 1 To size2 Do
Begin
Trest := FGInt1.Number + FGInt2.Number + rest;
Sum.Number := Trest And 2147483647;
rest := Trest Shr 31;
End;
For i := (size2 + 1) To size1 Do
Begin
Trest := FGInt1.Number + rest;
Sum.Number := Trest And 2147483647;
rest := Trest Shr 31;
End;
size := size1 + 1;
Sum.Number[0] := size;
Sum.Number[size] := rest;
While (Sum.Number[size] = 0) And (size > 1) Do size := size - 1;
If Sum.Number[0] > size Then SetLength(Sum.Number, size + 1);
Sum.Number[0] := size;
End
Else
Begin
If FGIntCompareAbs(FGInt2, FGInt1) = Lt Then FGIntAdd(FGInt2, FGInt1, Sum)
Else
Begin
SetLength(Sum.Number, size1 + 1);
rest := 0;
For i := 1 To size2 Do
Begin
Trest := 2147483648 + FGInt1.Number - FGInt2.Number + rest;
Sum.Number := Trest And 2147483647;
If (Trest > 2147483647) Then rest := 0 Else rest := -1;
End;
For i := (size2 + 1) To size1 Do
Begin
Trest := 2147483648 + FGInt1.Number + rest;
Sum.Number := Trest And 2147483647;
If (Trest > 2147483647) Then rest := 0 Else rest := -1;
End;
size := size1;
While (Sum.Number[size] = 0) And (size > 1) Do size := size - 1;
If size < size1 Then
Begin
SetLength(Sum.Number, size + 1);
End;
Sum.Number[0] := size;
Sum.Sign := FGInt1.Sign;
End;
End;
End;
End;


Procedure FGIntChangeSign(Var FGInt : TFGInt);
Begin
If FGInt.Sign = negative Then FGInt.Sign := positive Else FGInt.Sign := negative;
End;


// Substract 2 FGInts, FGInt1 - FGInt2 = dif

Procedure FGIntSub(Var FGInt1, FGInt2, dif : TFGInt);
Begin
FGIntChangeSign(FGInt2);
FGIntAdd(FGInt1, FGInt2, dif);
FGIntChangeSign(FGInt2);
End;


// multiply a FGInt by an integer, FGInt * by = res, by < 1000000000

Procedure FGIntMulByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64);
Var
i, size : longint;
Trest, rest : int64;
Begin
size := FGInt.Number[0];
SetLength(res.Number, size + 2);
rest := 0;
For i := 1 To size Do
Begin
Trest := FGInt.Number * by + rest;
res.Number := Trest And 2147483647;
rest := Trest Shr 31;
End;
If rest <> 0 Then
Begin
size := size + 1;
Res.Number[size] := rest;
End
Else SetLength(Res.Number, size + 1);
Res.Number[0] := size;
Res.Sign := FGInt.Sign;
End;


// multiply a FGInt by an integer, FGInt * by = res, by < 1000000000

Procedure FGIntMulByIntbis(Var FGInt : TFGInt; by : int64);
Var
i, size : longint;
Trest, rest : int64;
Begin
size := FGInt.Number[0];
SetLength(FGInt.Number, size + 2);
rest := 0;
For i := 1 To size Do
Begin
Trest := FGInt.Number * by + rest;
FGInt.Number := Trest And 2147483647;
rest := Trest Shr 31;
End;
If rest <> 0 Then
Begin
size := size + 1;
FGInt.Number[size] := rest;
End
Else SetLength(FGInt.Number, size + 1);
FGInt.Number[0] := size;
End;


// divide a FGInt by an integer, FGInt = res * by + modres

Procedure FGIntDivByInt(Const FGInt : TFGInt; Var res : TFGInt; by : int64; Var modres : int64);
Var
i, size : longint;
rest : int64;
Begin
size := FGInt.Number[0];
SetLength(res.Number, size + 1);
modres := 0;
For i := size Downto 1 Do
Begin
modres := modres Shl 31;
rest := modres Or FGInt.Number;
res.Number := rest Div by;
modres := rest Mod by;
End;
While (res.Number[size] = 0) And (size > 1) Do size := size - 1;
SetLength(res.Number, size + 1);
res.Number[0] := size;
Res.Sign := FGInt.Sign;
End;


// divide a FGInt by an integer, FGInt = FGInt * by + modres

Procedure FGIntDivByIntBis(Var FGInt : TFGInt; by : int64; Var modres : int64);
Var
i, size : longint;
rest : int64;
Begin
size := FGInt.Number[0];
modres := 0;
For i := size Downto 1 Do
Begin
modres := modres Shl 31;
rest := modres Or FGInt.Number;
FGInt.Number := rest Div by;
modres := rest Mod by;
End;
While (FGInt.Number[size] = 0) And (size > 1) Do size := size - 1;
If size <> FGInt.Number[0] Then
Begin
SetLength(FGInt.Number, size + 1);
FGInt.Number[0] := size;
End;
End;


// Reduce a FGInt modulo by (=an integer), FGInt mod by = modres

Procedure FGIntModByInt(Const FGInt : TFGInt; by : int64; Var modres : int64);
Var
i, size : longint;
rest : int64;
Begin
size := FGInt.Number[0];
modres := 0;
For i := size Downto 1 Do
Begin
modres := modres Shl 31;
rest := modres + FGInt.Number;
modres := rest Mod by;
End;
End;


// Returns the FGInt in absolute value

Procedure FGIntAbs(Var FGInt : TFGInt);
Begin
FGInt.Sign := positive;
End;


// Copy a FGInt1 into FGInt2

Procedure FGIntCopy(Const FGInt1 : TFGInt; Var FGInt2 : TFGInt);
Begin
FGInt2.Sign := FGInt1.Sign;
FGInt2.Number := Nil;
FGInt2.Number := Copy(FGInt1.Number, 0, FGInt1.Number[0] + 1);
End;


// Shift the FGInt to the left in base 2 notation, ie FGInt = FGInt * 2

Procedure FGIntShiftLeft(Var FGInt : TFGInt);
Var
l, m : int64;
i, size : longint;
Begin
size := FGInt.Number[0];
l := 0;
For i := 1 To Size Do
Begin
m := FGInt.Number Shr 30;
FGInt.Number := ((FGInt.Number Shl 1) Or l) And 2147483647;
l := m;
End;
If l <> 0 Then
Begin
setlength(FGInt.Number, size + 2);
FGInt.Number[size + 1] := l;
FGInt.Number[0] := size + 1;
End;
End;


// Shift the FGInt to the right in base 2 notation, ie FGInt = FGInt div 2

Procedure FGIntShiftRight(Var FGInt : TFGInt);
Var
l, m : int64;
i, size : longint;
Begin
size := FGInt.Number[0];
l := 0;
For i := size Downto 1 Do
Begin
m := FGInt.Number And 1;
FGInt.Number := (FGInt.Number Shr 1) Or l;
l := m Shl 30;
End;
If (FGInt.Number[size] = 0) And (size > 1) Then
Begin
setlength(FGInt.Number, size);
FGInt.Number[0] := size - 1;
End;
End;


// FGInt = FGInt / 2147483648

Procedure FGIntShiftRightBy31(Var FGInt : TFGInt);
Var
size : longint;
Begin
size := FGInt.Number[0];
If size > 1 Then
Begin
FGInt.Number := Copy(FGInt.Number, 1, Size);
FGInt.Number[0] := size - 1;
End
Else FGInt.Number[1] := 0;
End;


// FGInt1 = FGInt1 + FGInt2, FGInt1 > FGInt2

Procedure FGIntAddBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt);
Var
i, size1, size2 : longint;
rest : integer;
Trest : int64;
Begin
size1 := FGInt1.Number[0];
size2 := FGInt2.Number[0];
rest := 0;
For i := 1 To size2 Do
Begin
Trest := FGInt1.Number + FGInt2.Number + rest;
rest := Trest Shr 31;
FGInt1.Number := Trest And 2147483647;
End;
For i := size2 + 1 To size1 Do
Begin
Trest := FGInt1.Number + rest;
rest := Trest Shr 31;
FGInt1.Number := Trest And 2147483647;
End;
If rest <> 0 Then
Begin
SetLength(FGInt1.Number, size1 + 2);
FGInt1.Number[0] := size1 + 1;
FGInt1.Number[size1 + 1] := rest;
End;
End;


// FGInt1 = FGInt1 - FGInt2, use only when 0 < FGInt2 < FGInt1

Procedure FGIntSubBis(Var FGInt1 : TFGInt; Const FGInt2 : TFGInt);
Var
i, size1, size2 : longint;
rest : integer;
Trest : int64;
Begin
size1 := FGInt1.Number[0];
size2 := FGInt2.Number[0];
rest := 0;
For i := 1 To size2 Do
Begin
Trest := 2147483648 + FGInt1.Number - FGInt2.Number + rest;
If (Trest > 2147483647) Then rest := 0 Else rest := -1;
FGInt1.Number := Trest And 2147483647;
End;
For i := size2 + 1 To size1 Do
Begin
Trest := 2147483648 + FGInt1.Number + rest;
If (Trest > 2147483647) Then rest := 0 Else rest := -1;
FGInt1.Number := Trest And 2147483647;
End;
i := size1;
While (FGInt1.Number = 0) And (i > 1) Do i := i - 1;
If i < size1 Then
Begin
SetLength(FGInt1.Number, i + 1);
FGInt1.Number[0] := i;
End;
End;


// Multiply 2 FGInts, FGInt1 * FGInt2 = Prod

Procedure FGIntMul(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt);
Var
i, j, size, size1, size2 : longint;
rest, Trest : int64;
Begin
size1 := FGInt1.Number[0];
size2 := FGInt2.Number[0];
size := size1 + size2;
SetLength(Prod.Number, size + 1);
For i := 1 To size Do Prod.Number := 0;

For i := 1 To size2 Do
Begin
rest := 0;
For j := 1 To size1 Do
Begin
Trest := Prod.Number[j + i - 1] + FGInt1.Number[j] * FGInt2.Number + rest;
Prod.Number[j + i - 1] := Trest And 2147483647;
rest := Trest Shr 31;
End;
Prod.Number[i + size1] := rest;
End;

Prod.Number[0] := size;
While (Prod.Number[size] = 0) And (size > 1) Do size := size - 1;
If size < Prod.Number[0] Then
Begin
SetLength(Prod.Number, size + 1);
Prod.Number[0] := size;
End;
If FGInt1.Sign = FGInt2.Sign Then Prod.Sign := Positive Else prod.Sign := negative;
End;


// Square a FGInt, FGInt?= Square

Procedure FGIntSquare(Const FGInt : TFGInt; Var Square : TFGInt);
Var
size, size1, i, j : longint;
rest, Trest : int64;
Begin
size1 := FGInt.Number[0];
size := 2 * size1;
SetLength(Square.Number, size + 1);
Square.Number[0] := size;
For i := 1 To size Do Square.Number := 0;
For i := 1 To size1 Do
Begin
Trest := Square.Number[2 * i - 1] + FGInt.Number * FGInt.Number;
Square.Number[2 * i - 1] := Trest And 2147483647;
rest := Trest Shr 31;
For j := i + 1 To size1 Do
Begin
Trest := Square.Number[i + j - 1] + 2 * FGInt.Number * FGInt.Number[j] + rest;
Square.Number[i + j - 1] := Trest And 2147483647;
rest := Trest Shr 31;
End;
Square.Number[i + size1] := rest;
End;
Square.Sign := positive;
While (Square.Number[size] = 0) And (size > 1) Do size := size - 1;
If size < 2 * size1 Then
Begin
SetLength(Square.Number, size + 1);
Square.Number[0] := size;
End;
End;


// Convert a FGInt to a binary string (base 2) & visa versa

Procedure FGIntToBase2String(Const FGInt : TFGInt; Var S : String);
Var
i : longint;
j : integer;
Begin
S := '';
For i := 1 To FGInt.Number[0] Do
Begin
For j := 0 To 30 Do S := inttostr(1 And (FGInt.Number Shr j)) + S;
End;
While (length(S) > 1) And (S[1] = '0') Do delete(S, 1, 1);
If S = '' Then S := '0';
End;


Procedure Base2StringToFGInt(S : String; Var FGInt : TFGInt);
Var
i, j, size : longint;
Begin
while (S[1]='0') and (length(S)>1) do delete(S,1,1);
size := length(S) Div 31;
If (length(S) Mod 31) <> 0 Then size := size + 1;
SetLength(FGInt.Number, size + 1);
FGInt.Number[0] := size;
j := 1;
FGInt.Number[j] := 0;
i := 0;
While length(S) > 0 Do
Begin
If S[length(S)] = '1' Then
FGInt.Number[j] := FGInt.Number[j] Or (1 Shl i);
i := i + 1;
If i = 31 Then
Begin
i := 0;
j := j + 1;
If j <= size Then FGInt.Number[j] := 0;
End;
delete(S, length(S), 1);
End;
FGInt.Sign := positive;
End;


// Convert a FGInt to an base 256 string & visa versa

Procedure FGIntToBase256String(Const FGInt : TFGInt; Var str256 : String);
Var
temp1 : String;
i, len8 : longint;
g : char;
Begin
FGIntToBase2String(FGInt, temp1);
While (length(temp1) Mod 8) <> 0 Do temp1 := '0' + temp1;
len8 := length(temp1) Div 8;
str256 := '';
For i := 1 To len8 Do
Begin
zeronetochar8(g, copy(temp1, 1, 8));
str256 := str256 + g;
delete(temp1, 1, 8);
End;
End;


Procedure Base256StringToFGInt(str256 : String; Var FGInt : TFGInt);
Var
temp1 : String;
i : longint;
trans : Array[0..255] Of String;
Begin
temp1 := '';
initialize8(trans);
For i := 1 To length(str256) Do temp1 := temp1 + trans[ord(str256)];
While (temp1[1] = '0') And (temp1 <> '0') Do delete(temp1, 1, 1);
Base2StringToFGInt(temp1, FGInt);
End;

// Convert an MPI (Multiple Precision Integer, PGP style) to an FGInt &
// visa versa

Procedure PGPMPIToFGInt(PGPMPI : String; Var FGInt : TFGInt);
Var
temp : String;
Begin
temp := PGPMPI;
delete(temp, 1, 2);
Base256StringToFGInt(temp, FGInt);
End;


Procedure FGIntToPGPMPI(FGInt : TFGInt; Var PGPMPI : String);
Var
len, i : word;
c : char;
b : byte;
Begin
FGIntToBase256String(FGInt, PGPMPI);
len := length(PGPMPI) * 8;
c := PGPMPI[1];
For i := 7 Downto 0 Do If (ord(c) Shr i) = 0 Then len := len - 1 Else break;
b := len Mod 256;
PGPMPI := chr(b) + PGPMPI;
b := len Div 256;
PGPMPI := chr(b) + PGPMPI;
End;


// Exponentiate a FGInt, FGInt^exp = res

Procedure FGIntExp(Const FGInt, exp : TFGInt; Var res : TFGInt);
Var
temp2, temp3 : TFGInt;
S : String;
i : longint;
Begin
FGIntToBase2String(exp, S);
If S[length(S)] = '0' Then Base10StringToFGInt('1', res) Else FGIntCopy(FGInt, res);
FGIntCopy(FGInt, temp2);
If length(S) > 1 Then
For i := (length(S) - 1) Downto 1 Do
Begin
FGIntSquare(temp2, temp3);
FGIntCopy(temp3, temp2);
If S = '1' Then
Begin
FGIntMul(res, temp2, temp3);
FGIntCopy(temp3, res);
End;
End;
End;


// Compute FGInt! = FGInt * (FGInt - 1) * (FGInt - 2) * ... * 3 * 2 * 1

Procedure FGIntFac(Const FGInt : TFGInt; Var res : TFGInt);
Var
one, temp, temp1 : TFGInt;
Begin
FGIntCopy(FGInt, temp);
Base10StringToFGInt('1', res);
Base10StringToFGInt('1', one);

While Not (FGIntCompareAbs(temp, one) = Eq) Do
Begin
FGIntMul(temp, res, temp1);
FGIntCopy(temp1, res);
FGIntSubBis(temp, one);
End;

FGIntDestroy(one);
FGIntDestroy(temp);
End;


// FGInt = FGInt * 2147483648

Procedure FGIntShiftLeftBy31(Var FGInt : TFGInt);
Var
f1, f2 : int64;
i, size : longint;
Begin
size := FGInt.Number[0];
SetLength(FGInt.Number, size + 2);
f1 := 0;
For i := 1 To (size + 1) Do
Begin
f2 := FGInt.Number;
FGInt.Number := f1;
f1 := f2;
End;
FGInt.Number[0] := size + 1;
End;


// Divide 2 FGInts, FGInt1 = FGInt2 * QFGInt + MFGInt, MFGInt is always positive

Procedure FGIntDivMod(Var FGInt1, FGInt2, QFGInt, MFGInt : TFGInt);
Var
one, zero, temp1, temp2 : TFGInt;
s1, s2 : TSign;
i, j, s, t : longint;
Begin
s1 := FGInt1.Sign;
s2 := FGInt2.Sign;
FGIntAbs(FGInt1);
FGIntAbs(FGInt2);
FGIntCopy(FGInt1, MFGInt);
FGIntCopy(FGInt2, temp1);

If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
Begin
s := FGInt1.Number[0] - FGInt2.Number[0];
setlength(QFGInt.Number, s + 2);
QFGInt.Number[0] := s + 1;
For t := 1 To s Do
Begin
FGIntShiftLeftBy31(temp1);
QFGInt.Number[t] := 0;
End;
j := s + 1;
QFGInt.Number[j] := 0;
While FGIntCompareAbs(MFGInt, FGInt2) <> St Do
Begin
While FGIntCompareAbs(MFGInt, temp1) <> St Do
Begin
If MFGInt.Number[0] > temp1.Number[0] Then
i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number[MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1)
Else i := MFGInt.Number[MFGInt.Number[0]] Div (temp1.Number[temp1.Number[0]] + 1);
If (i <> 0) Then
Begin
FGIntCopy(temp1, temp2);
FGIntMulByIntBis(temp2, i);
FGIntSubBis(MFGInt, temp2);
QFGInt.Number[j] := QFGInt.Number[j] + i;
If FGIntCompareAbs(MFGInt, temp2) <> St Then
Begin
QFGInt.Number[j] := QFGInt.Number[j] + i;
FGIntSubBis(MFGInt, temp2);
End;
End Else
Begin
QFGInt.Number[j] := QFGInt.Number[j] + 1;
FGIntSubBis(MFGInt, temp1);
End;
End;
If MFGInt.Number[0] <= temp1.Number[0] Then
If FGIntCompareAbs(temp1, FGInt2) <> Eq Then
Begin
FGIntShiftRightBy31(temp1);
j := j - 1;
End;
End;
End
Else Base10StringToFGInt('0', QFGInt);
s := QFGInt.Number[0];
While (s > 1) And (QFGInt.Number = 0) Do s := s - 1;
If s < QFGInt.Number[0] Then
Begin
setlength(QFGInt.Number, s + 1);
QFGInt.Number[0] := s;
End;
QFGInt.Sign := positive;

FGIntDestroy(temp1);
Base10StringToFGInt('0', zero);
Base10StringToFGInt('1', one);
If s1 = negative Then
Begin
If FGIntCompareAbs(MFGInt, zero) <> Eq Then
Begin
FGIntadd(QFGInt, one, temp1);
FGIntCopy(temp1, QFGInt);
FGIntDestroy(temp1);
FGIntsub(FGInt2, MFGInt, temp1);
FGIntCopy(temp1, MFGInt);
End;
If s2 = positive Then QFGInt.Sign := negative;
End
Else QFGInt.Sign := s2;
FGIntDestroy(one);
FGIntDestroy(zero);

FGInt1.Sign := s1;
FGInt2.Sign := s2;
End;


// Same as above but doesn 't compute MFGInt

Procedure FGIntDiv(Var FGInt1, FGInt2, QFGInt : TFGInt);
Var
one, zero, temp1, temp2, MFGInt : TFGInt;
s1, s2 : TSign;
i, j, s, t : longint;
Begin
s1 := FGInt1.Sign;
s2 := FGInt2.Sign;
FGIntAbs(FGInt1);
FGIntAbs(FGInt2);
FGIntCopy(FGInt1, MFGInt);
FGIntCopy(FGInt2, temp1);

If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
Begin
s := FGInt1.Number[0] - FGInt2.Number[0];
setlength(QFGInt.Number, s + 2);
QFGInt.Number[0] := s + 1;
For t := 1 To s Do
Begin
FGIntShiftLeftBy31(temp1);
QFGInt.Number[t] := 0;
End;
j := s + 1;
QFGInt.Number[j] := 0;
While FGIntCompareAbs(MFGInt, FGInt2) <> St Do
Begin
While FGIntCompareAbs(MFGInt, temp1) <> St Do
Begin
If MFGInt.Number[0] > temp1.Number[0] Then
i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number[MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1)
Else i := MFGInt.Number[MFGInt.Number[0]] Div (temp1.Number[temp1.Number[0]] + 1);
If (i <> 0) Then
Begin
FGIntCopy(temp1, temp2);
FGIntMulByIntBis(temp2, i);
FGIntSubBis(MFGInt, temp2);
QFGInt.Number[j] := QFGInt.Number[j] + i;
If FGIntCompareAbs(MFGInt, temp2) <> St Then
Begin
QFGInt.Number[j] := QFGInt.Number[j] + i;
FGIntSubBis(MFGInt, temp2);
End;
End Else
Begin
QFGInt.Number[j] := QFGInt.Number[j] + 1;
FGIntSubBis(MFGInt, temp1);
End;
End;
If MFGInt.Number[0] <= temp1.Number[0] Then
If FGIntCompareAbs(temp1, FGInt2) <> Eq Then
Begin
FGIntShiftRightBy31(temp1);
j := j - 1;
End;
End;
End
Else Base10StringToFGInt('0', QFGInt);
s := QFGInt.Number[0];
While (s > 1) And (QFGInt.Number = 0) Do s := s - 1;
If s < QFGInt.Number[0] Then
Begin
setlength(QFGInt.Number, s + 1);
QFGInt.Number[0] := s;
End;
QFGInt.Sign := positive;

FGIntDestroy(temp1);
Base10StringToFGInt('0', zero);
Base10StringToFGInt('1', one);
If s1 = negative Then
Begin
If FGIntCompareAbs(MFGInt, zero) <> Eq Then
Begin
FGIntadd(QFGInt, one, temp1);
FGIntCopy(temp1, QFGInt);
FGIntDestroy(temp1);
FGIntsub(FGInt2, MFGInt, temp1);
FGIntCopy(temp1, MFGInt);
End;
If s2 = positive Then QFGInt.Sign := negative;
End
Else QFGInt.Sign := s2;
FGIntDestroy(one);
FGIntDestroy(zero);
FGIntDestroy(MFGInt);

FGInt1.Sign := s1;
FGInt2.Sign := s2;
End;


// Same as above but this computes MFGInt in stead of QFGInt
// MFGInt = FGInt1 mod FGInt2

Procedure FGIntMod(Var FGInt1, FGInt2, MFGInt : TFGInt);
Var
one, zero, temp1, temp2 : TFGInt;
s1, s2 : TSign;
i : int64;
s, t : longint;
Begin
s1 := FGInt1.Sign;
s2 := FGInt2.Sign;
FGIntAbs(FGInt1);
FGIntAbs(FGInt2);
FGIntCopy(FGInt1, MFGInt);
FGIntCopy(FGInt2, temp1);

If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
Begin
s := FGInt1.Number[0] - FGInt2.Number[0];
For t := 1 To s Do FGIntShiftLeftBy31(temp1);
While FGIntCompareAbs(MFGInt, FGInt2) <> St Do
Begin
While FGIntCompareAbs(MFGInt, temp1) <> St Do
Begin
If MFGInt.Number[0] > temp1.Number[0] Then
i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number[MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1)
Else i := MFGInt.Number[MFGInt.Number[0]] Div (temp1.Number[temp1.Number[0]] + 1);
If (i <> 0) Then
Begin
FGIntCopy(temp1, temp2);
FGIntMulByIntBis(temp2, i);
FGIntSubBis(MFGInt, temp2);
If FGIntCompareAbs(MFGInt, temp2) <> St Then FGIntSubBis(MFGInt, temp2);
End Else FGIntSubBis(MFGInt, temp1);
// If FGIntCompareAbs(MFGInt, temp1) <> St Then FGIntSubBis(MFGInt,temp1);
End;
If MFGInt.Number[0] <= temp1.Number[0] Then
If FGIntCompareAbs(temp1, FGInt2) <> Eq Then FGIntShiftRightBy31(temp1);
End;
End;

FGIntDestroy(temp1);
Base10StringToFGInt('0', zero);
Base10StringToFGInt('1', one);
If s1 = negative Then
Begin
If FGIntCompareAbs(MFGInt, zero) <> Eq Then
Begin
FGIntSub(FGInt2, MFGInt, temp1);
FGIntCopy(temp1, MFGInt);
End;
End;
FGIntDestroy(one);
FGIntDestroy(zero);

FGInt1.Sign := s1;
FGInt2.Sign := s2;
End;


// Square a FGInt modulo Modb, FGInt^2 mod Modb = FGIntSM

Procedure FGIntSquareMod(Var FGInt, Modb, FGIntSM : TFGInt);
Var
temp : TFGInt;
Begin
FGIntSquare(FGInt, temp);
FGIntMod(temp, Modb, FGIntSM);
FGIntDestroy(temp);
End;


// Add 2 FGInts modulo base, (FGInt1 + FGInt2) mod base = FGIntres

Procedure FGIntAddMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt);
Var
temp : TFGInt;
Begin
FGIntadd(FGInt1, FGInt2, temp);
FGIntMod(temp, base, FGIntres);
FGIntDestroy(temp);
End;


// Multiply 2 FGInts modulo base, (FGInt1 * FGInt2) mod base = FGIntres

Procedure FGIntMulMod(Var FGInt1, FGInt2, base, FGIntres : TFGInt);
Var
temp : TFGInt;
Begin
FGIntMul(FGInt1, FGInt2, temp);
FGIntMod(temp, base, FGIntres);
FGIntDestroy(temp);
End;


// Exponentiate 2 FGInts modulo base, (FGInt1 ^ FGInt2) mod modb = res

Procedure FGIntModExp(Var FGInt, exp, modb, res : TFGInt);
Var
temp2, temp3 : TFGInt;
i : longint;
S : String;
Begin
If (Modb.Number[1] Mod 2) = 1 Then
Begin
FGIntMontgomeryModExp(FGInt, exp, modb, res);
exit;
End;
FGIntToBase2String(exp, S);
Base10StringToFGInt('1', res);
FGIntcopy(FGInt, temp2);

For i := length(S) Downto 1 Do
Begin
If S = '1' Then
Begin
FGIntmulMod(res, temp2, modb, temp3);
FGIntCopy(temp3, res);
End;
FGIntSquareMod(temp2, Modb, temp3);
FGIntCopy(temp3, temp2);
End;
FGIntDestroy(temp2);
End;


// Procedures for Montgomery Exponentiation

Procedure FGIntModBis(Const FGInt : TFGInt; Var FGIntOut : TFGInt; b : longint; head : int64);
Var
i : longint;
Begin
If b <= FGInt.Number[0] Then
Begin
FGIntOut.Number := Copy(FGInt.Number, 0, b + 1);
FGIntOut.Number := FGIntOut.Number And head;
i := b;
While (FGIntOut.Number = 0) And (i > 1) Do i := i - 1;
If i < b Then SetLength(FGIntOut.Number, i + 1);
FGIntOut.Number[0] := i;
FGIntOut.Sign := positive;
End Else FGIntCopy(FGInt, FGIntOut);
End;


Procedure FGIntMulModBis(Const FGInt1, FGInt2 : TFGInt; Var Prod : TFGInt; b : longint; head : int64);
Var
i, j, size, size1, size2, t : longint;
rest, Trest : int64;
Begin
size1 := FGInt1.Number[0];
size2 := FGInt2.Number[0];
size := min(b, size1 + size2);
SetLength(Prod.Number, size + 1);
For i := 1 To size Do Prod.Number := 0;

For i := 1 To size2 Do
Begin
rest := 0;
t := min(size1, b - i + 1);
For j := 1 To t Do
Begin
Trest := Prod.Number[j + i - 1] + FGInt1.Number[j] * FGInt2.Number + rest;
Prod.Number[j + i - 1] := Trest And 2147483647;
rest := Trest Shr 31;
End;
If (i + size1) <= b Then Prod.Number[i + size1] := rest;
End;

Prod.Number[0] := size;
If size = b Then Prod.Number := Prod.Number And head;
While (Prod.Number[size] = 0) And (size > 1) Do size := size - 1;
If size < Prod.Number[0] Then
Begin
SetLength(Prod.Number, size + 1);
Prod.Number[0] := size;
End;
If FGInt1.Sign = FGInt2.Sign Then Prod.Sign := Positive Else prod.Sign := negative;
End;


Procedure FGIntMontgomeryMod(Const GInt, base, baseInv : TFGInt; Var MGInt : TFGInt; b : longint; head : int64);
Var
m, temp, temp1 : TFGInt;
r : int64;
Begin
FGIntModBis(GInt, temp, b, head);
FGIntMulModBis(temp, baseInv, m, b, head);
FGIntMul(m, base, temp1);
FGIntDestroy(temp);
FGIntAdd(temp1, GInt, temp);
FGIntDestroy(temp1);
MGInt.Number := copy(temp.Number, b - 1, temp.Number[0] - b + 2);
MGInt.Sign := positive;
MGInt.Number[0] := temp.Number[0] - b + 1;
FGIntDestroy(temp);
If (head Shr 30) = 0 Then FGIntDivByIntBis(MGInt, head + 1, r)
Else FGIntShiftRightBy31(MGInt);
If FGIntCompareAbs(MGInt, base) <> St Then FGIntSubBis(MGInt, base);
FGIntDestroy(temp);
FGIntDestroy(m);
End;


Procedure FGIntMontgomeryModExp(Var FGInt, exp, modb, res : TFGInt);
Var
temp2, temp3, baseInv, r : TFGInt;
i, j, t, b : longint;
S : String;
head : int64;
Begin
FGIntToBase2String(exp, S);
t := modb.Number[0];
b := t;

If (modb.Number[t] Shr 30) = 1 Then t := t + 1;
setlength(r.Number, t + 1);
r.Number[0] := t;
r.Sign := positive;
For i := 1 To t Do r.Number := 0;
If t = modb.Number[0] Then
Begin
head := 2147483647;
For j := 29 Downto 0 Do
Begin
head := head Shr 1;
If (modb.Number[t] Shr j) = 1 Then
Begin
r.Number[t] := 1 Shl (j + 1);
break;
End;
End;
End
Else
Begin
r.Number[t] := 1;
head := 2147483647;
End;

FGIntModInv(modb, r, temp2);
If temp2.Sign = negative Then FGIntCopy(temp2, BaseInv)
Else
Begin
FGIntCopy(r, BaseInv);
FGIntSubBis(BaseInv, temp2);
End;
// FGIntBezoutBachet(r, modb, temp2, BaseInv);
FGIntAbs(BaseInv);
FGIntDestroy(temp2);
FGIntMod(r, modb, res);
FGIntMulMod(FGInt, res, modb, temp2);
FGIntDestroy(r);

For i := length(S) Downto 1 Do
Begin
If S = '1' Then
Begin
FGIntmul(res, temp2, temp3);
FGIntDestroy(res);
FGIntMontgomeryMod(temp3, modb, baseinv, res, b, head);
FGIntDestroy(temp3);
End;
FGIntSquare(temp2, temp3);
FGIntDestroy(temp2);
FGIntMontgomeryMod(temp3, modb, baseinv, temp2, b, head);
FGIntDestroy(temp3);
End;
FGIntDestroy(temp2);
FGIntMontgomeryMod(res, modb, baseinv, temp3, b, head);
FGIntCopy(temp3, res);
FGIntDestroy(temp3);
FGIntDestroy(baseinv);
End;


// Compute the Greatest Common Divisor of 2 FGInts

Procedure FGIntGCD(Const FGInt1, FGInt2 : TFGInt; Var GCD : TFGInt);
Var
k : TCompare;
zero, temp1, temp2, temp3 : TFGInt;
Begin
k := FGIntCompareAbs(FGInt1, FGInt2);
If (k = Eq) Then FGIntCopy(FGInt1, GCD) Else
If (k = St) Then FGIntGCD(FGInt2, FGInt1, GCD) Else
Begin
Base10StringToFGInt('0', zero);
FGIntCopy(FGInt1, temp1);
FGIntCopy(FGInt2, temp2);
While (temp2.Number[0] <> 1) Or (temp2.Number[1] <> 0) Do
Begin
FGIntMod(temp1, temp2, temp3);
FGIntCopy(temp2, temp1);
FGIntCopy(temp3, temp2);
FGIntDestroy(temp3);
End;
FGIntCopy(temp1, GCD);
FGIntDestroy(temp2);
FGIntDestroy(zero);
End;
End;


// Compute the Least Common Multiple of 2 FGInts

Procedure FGIntLCM(Const FGInt1, FGInt2 : TFGInt; Var LCM : TFGInt);
Var
temp1, temp2 : TFGInt;
Begin
FGIntGCD(FGInt1, FGInt2, temp1);
FGIntmul(FGInt1, FGInt2, temp2);
FGIntdiv(temp2, temp1, LCM);
FGIntDestroy(temp1);
FGIntDestroy(temp2);
End;


// Trialdivision of a FGInt upto 9999 and stopping when a divisor is found, returning ok=false

Procedure FGIntTrialDiv9999(Const FGInt : TFGInt; Var ok : boolean);
Var
j : int64;
i : integer;
Begin
If ((FGInt.Number[1] Mod 2) = 0) Then ok := false
Else
Begin
i := 0;
ok := true;
While ok And (i < 1228) Do
Begin
i := i + 1;
FGIntmodbyint(FGInt, primes, j);
If j = 0 Then ok := false;
End;
End;
End;


// A prng

Procedure FGIntRandom1(Var Seed, RandomFGInt : TFGInt);
Var
temp, base : TFGInt;
Begin
Base10StringToFGInt('281474976710656', base);
Base10StringToFGInt('44485709377909', temp);
FGIntMulMod(seed, temp, base, RandomFGInt);
FGIntDestroy(temp);
FGIntDestroy(base);
End;


// Perform a Rabin Miller Primality Test nrtest times on FGIntp, returns ok=true when FGIntp passes the test

Procedure FGIntRabinMiller(Var FGIntp : TFGInt; nrtest : integer; Var ok : boolean);
Var
j, b, i : int64;
m, z, temp1, temp2, temp3, zero, one, two, pmin1 : TFGInt;
ok1, ok2 : boolean;
Begin
randomize;
j := 0;
Base10StringToFGInt('0', zero);
Base10StringToFGInt('1', one);
Base10StringToFGInt('2', two);
FGIntsub(FGIntp, one, temp1);
FGIntsub(FGIntp, one, pmin1);

b := 0;
While (temp1.Number[1] Mod 2) = 0 Do
Begin
b := b + 1;
FGIntShiftRight(temp1);
End;
m := temp1;

i := 0;
ok := true;
Randomize;
While (i < nrtest) And ok Do
Begin
i := i + 1;
Base10StringToFGInt(inttostr(Primes[Random(1227) + 1]), temp2);
FGIntMontGomeryModExp(temp2, m, FGIntp, z);
FGIntDestroy(temp2);
ok1 := (FGIntCompareAbs(z, one) = Eq);
ok2 := (FGIntCompareAbs(z, pmin1) = Eq);
If Not (ok1 Or ok2) Then
Begin

While (ok And (j < b)) Do
Begin
If (j > 0) And ok1 Then ok := false
Else
Begin
j := j + 1;
If (j < b) And (Not ok2) Then
Begin
FGIntSquaremod(z, FGIntp, temp3);
FGIntCopy(temp3, z);
ok1 := (FGIntCompareAbs(z, one) = Eq);
ok2 := (FGIntCompareAbs(z, pmin1) = Eq);
If ok2 Then j := b;
End
Else If (Not ok2) And (j >= b) Then ok := false;
End;
End;

End
End;

FGIntDestroy(zero);
FGIntDestroy(one);
FGIntDestroy(two);
FGIntDestroy(m);
FGIntDestroy(z);
FGIntDestroy(pmin1);
End;


// Compute the coefficients from the Bezout Bachet theorem, FGInt1 * a + FGInt2 * b = GCD(FGInt1, FGInt2)

Procedure FGIntBezoutBachet(Var FGInt1, FGInt2, a, b : TFGInt);
Var
zero, r1, r2, r3, ta, gcd, temp, temp1, temp2 : TFGInt;
Begin
If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
Begin
FGIntcopy(FGInt1, r1);
FGIntcopy(FGInt2, r2);
Base10StringToFGInt('0', zero);
Base10StringToFGInt('1', a);
Base10StringToFGInt('0', ta);

Repeat
FGIntdivmod(r1, r2, temp, r3);
FGIntDestroy(r1);
r1 := r2;
r2 := r3;

FGIntmul(ta, temp, temp1);
FGIntsub(a, temp1, temp2);
FGIntCopy(ta, a);
FGIntCopy(temp2, ta);
FGIntDestroy(temp1);

FGIntDestroy(temp);
Until FGIntCompareAbs(r3, zero) = Eq;

FGIntGCD(FGInt1, FGInt2, gcd);
FGIntmul(a, FGInt1, temp1);
FGIntsub(gcd, temp1, temp2);
FGIntDestroy(temp1);
FGIntdiv(temp2, FGInt2, b);
FGIntDestroy(temp2);

FGIntDestroy(ta);
FGIntDestroy(r1);
FGIntDestroy(r2);
FGIntDestroy(gcd);
End
Else FGIntBezoutBachet(FGInt2, FGInt1, b, a);
End;


// Find the (multiplicative) Modular inverse of a FGInt in a finite ring
// of additive order base

Procedure FGIntModInv(Const FGInt1, base : TFGInt; Var Inverse : TFGInt);
Var
zero, one, r1, r2, r3, tb, gcd, temp, temp1, temp2 : TFGInt;
Begin
Base10StringToFGInt('1', one);
FGIntGCD(FGInt1, base, gcd);
If FGIntCompareAbs(one, gcd) = Eq Then
Begin
FGIntcopy(base, r1);
FGIntcopy(FGInt1, r2);
Base10StringToFGInt('0', zero);
Base10StringToFGInt('0', inverse);
Base10StringToFGInt('1', tb);

Repeat
FGIntDestroy(r3);
FGIntdivmod(r1, r2, temp, r3);
FGIntCopy(r2, r1);
FGIntCopy(r3, r2);

FGIntmul(tb, temp, temp1);
FGIntsub(inverse, temp1, temp2);
FGIntDestroy(inverse);
FGIntDestroy(temp1);
FGIntCopy(tb, inverse);
FGIntCopy(temp2, tb);

FGIntDestroy(temp);
Until FGIntCompareAbs(r3, zero) = Eq;

If inverse.Sign = negative Then
Begin
FGIntadd(base, inverse, temp);
FGIntCopy(temp, inverse);
End;

FGIntDestroy(tb);
FGIntDestroy(r1);
FGIntDestroy(r2);
End;
FGIntDestroy(gcd);
FGIntDestroy(one);
End;


// Perform a (combined) primality test on FGIntp consisting of a trialdivision upto 8192,
// if the FGInt passes perform nrRMtests Rabin Miller primality tests, returns ok when a
// FGInt is probably prime

Procedure FGIntPrimetest(Var FGIntp : TFGInt; nrRMtests : integer; Var ok : boolean);
Begin
FGIntTrialdiv9999(FGIntp, ok);
If ok Then FGIntRabinMiller(FGIntp, nrRMtests, ok);
End;


// Computes the Legendre symbol for a any number and
// p a prime, returns 0 if p divides a, 1 if a is a
// quadratic residu mod p, -1 if a is a quadratic
// nonresidu mod p

Procedure FGIntLegendreSymbol(Var a, p : TFGInt; Var L : integer);
Var
temp1, temp2, temp3, temp4, temp5, zero, one : TFGInt;
i : int64;
ok1, ok2 : boolean;
Begin
Base10StringToFGInt('0', zero);
Base10StringToFGInt('1', one);
FGIntMod(a, p, temp1);
If FGIntCompareAbs(zero, temp1) = Eq Then
Begin
FGIntDestroy(temp1);
L := 0;
End
Else
Begin
FGIntDestroy(temp1);
FGIntCopy(p, temp1);
FGIntCopy(a, temp2);
L := 1;
While FGIntCompareAbs(temp2, one) <> Eq Do
Begin
If (temp2.Number[1] Mod 2) = 0 Then
Begin
FGIntSquare(temp1, temp3);
FGIntSub(temp3, one, temp4);
FGIntDestroy(temp3);
FGIntDivByInt(temp4, temp3, 8, i);
If (temp3.Number[1] Mod 2) = 0 Then ok1 := false Else ok1 := true;
FGIntDestroy(temp3);
FGIntDestroy(temp4);
If ok1 = true Then L := L * (-1);
FGIntDivByIntBis(temp2, 2, i);
End
Else
Begin
FGIntSub(temp1, one, temp3);
FGIntSub(temp2, one, temp4);
FGIntMul(temp3, temp4, temp5);
FGIntDestroy(temp3);
FGIntDestroy(temp4);
FGIntDivByInt(temp5, temp3, 4, i);
If (temp3.Number[1] Mod 2) = 0 Then ok2 := false Else ok2 := true;
FGIntDestroy(temp5);
FGIntDestroy(temp3);
If ok2 = true Then L := L * (-1);
FGIntMod(temp1, temp2, temp3);
FGIntCopy(temp2, temp1);
FGIntCopy(temp3, temp2);
End;
End;
FGIntDestroy(temp1);
FGIntDestroy(temp2);
End;
FGIntDestroy(zero);
FGIntDestroy(one);
End;


// Compute a square root modulo a prime number
// SquareRoot^2 mod Prime = Square

Procedure FGIntSquareRootModP(Square, Prime : TFGInt; Var SquareRoot : TFGInt);
Var
one, n, b, s, r, temp, temp1, temp2, temp3 : TFGInt;
a, L, i, j : longint;
Begin
Base2StringToFGInt('1', one);
Base2StringToFGInt('10', n);
a := 0;
FGIntLegendreSymbol(n, Prime, L);
While L <> -1 Do
Begin
FGIntAddBis(n, one);
FGIntLegendreSymbol(n, Prime, L);
End;
FGIntCopy(Prime, s);
s.Number[1] := s.Number[1] - 1;
While (s.Number[1] Mod 2) = 0 Do
Begin
FGIntShiftRight(s);
a := a + 1;
End;
FGIntMontgomeryModExp(n, s, Prime, b);
FGIntAdd(s, one, temp);
FGIntShiftRight(temp);
FGIntMontgomeryModExp(Square, temp, Prime, r);
FGIntDestroy(temp);
FGIntModInv(Square, Prime, temp1);

For i := 0 To (a - 2) Do
Begin
FGIntSquareMod(r, Prime, temp2);
FGIntMulMod(temp1, temp2, Prime, temp);
FGIntDestroy(temp2);
For j := 1 To (a - i - 2) Do
Begin
FGIntSquareMod(temp, Prime, temp2);
FGIntDestroy(temp);
FGIntCopy(temp2, temp);
FGIntDestroy(temp2);
End;
If FGIntCompareAbs(temp, one) <> Eq Then
Begin
FGIntMulMod(r, b, Prime, temp3);
FGIntDestroy(r);
FGIntCopy(temp3, r);
FGIntDestroy(temp3);
End;
FGIntDestroy(temp);
FGIntDestroy(temp2);
If i = (a - 2) Then break;
FGIntSquareMod(b, Prime, temp3);
FGIntDestroy(b);
FGIntCopy(temp3, b);
FGIntDestroy(temp3);
End;

FGIntCopy(r, SquareRoot);
FGIntDestroy(r);
FGIntDestroy(s);
FGIntDestroy(b);
FGIntDestroy(temp1);
FGIntDestroy(one);
FGIntDestroy;
End;


End.

第二部分
{License, info, etc
------------------

This implementation is made by Walied Othman, to contact me
mail to Walied.Othman@Student.KULeuven.ac.be or
Triade@ace.Ulyssis.Student.KULeuven.ac.be,
always mention wether it 's about the FGInt for Delphi or for
FreePascal, or wether it 's about the 6xs, preferably in the subject line.
If you 're going to use these implementations, at least mention my
name or something and notify me so I may even put a link on my page.
This implementation is freeware and according to the coderpunks'
manifesto it should remain so, so don 't use these implementations
in commercial software. Encryption, as a tool to ensure privacy
should be free and accessible for anyone. If you plan to use these
implementations in a commercial application, contact me before
doing so, that way you can license the software to use it in commercial
Software. If any algorithm is patented in your country, you should
acquire a license before using this software. Modified versions of this
software must contain an acknowledgement of the original author (=me).
This implementaion is available at
http://ace.ulyssis.student.kuleuven.ac.be/~triade/

copyright 2000, Walied Othman
This header may not be removed.
}

Unit FGIntPrimeGeneration;

Interface

Uses Windows, SysUtils, Controls, FGInt;

Procedure PrimeSearch(Var GInt : TFGInt);

Implementation


{$H+}


// Does an incremental search for primes starting from GInt,
// when one is found, it is stored in GInt

Procedure PrimeSearch(Var GInt : TFGInt);
Var
temp, two : TFGInt;
ok : Boolean;
Begin
If (GInt.Number[1] Mod 2) = 0 Then GInt.Number[1] := GInt.Number[1] + 1;
Base10StringToFGInt('2', two);
ok := false;
While Not ok Do
Begin
FGIntAdd(GInt, two, temp);
FGIntCopy(temp, GInt);
FGIntPrimeTest(GInt, 4, ok);
End;
FGIntDestroy(two);
End;

End.

第三部分
{License, info, etc
------------------

This implementation is made by Walied Othman, to contact me
mail to Walied.Othman@Student.KULeuven.ac.be or
Triade@ace.Ulyssis.Student.KULeuven.ac.be,
always mention wether it 's about the FGInt for Delphi or for
FreePascal, or wether it 's about the 6xs, preferably in the subject line.
If you 're going to use these implementations, at least mention my
name or something and notify me so I may even put a link on my page.
This implementation is freeware and according to the coderpunks'
manifesto it should remain so, so don 't use these implementations
in commercial software. Encryption, as a tool to ensure privacy
should be free and accessible for anyone. If you plan to use these
implementations in a commercial application, contact me before
doing so, that way you can license the software to use it in commercial
Software. If any algorithm is patented in your country, you should
acquire a license before using this software. Modified versions of this
software must contain an acknowledgement of the original author (=me).
This implementaion is available at
http://ace.ulyssis.student.kuleuven.ac.be/~triade/

copyright 2000, Walied Othman
This header may not be removed.
}

Unit FGIntRSA;

Interface

Uses Windows, SysUtils, Controls, FGInt;

Procedure RSAEncrypt(P : String; Var exp, modb : TFGInt; Var E : String);
Procedure RSADecrypt(E : String; Var exp, modb, d_p, d_q, p, q : TFGInt; Var D : String);
Procedure RSASign(M : String; Var d, n, dp, dq, p, q : TFGInt; Var S : String);
Procedure RSAVerify(M, S : String; Var e, n : TFGInt; Var valid : boolean);


Implementation


{$H+}




// Encrypt a string with the RSA algorithm, P^exp mod modb = E

Procedure RSAEncrypt(P : String; Var exp, modb : TFGInt; Var E : String);
Var
i, j, modbits : longint;
PGInt, temp, zero : TFGInt;
tempstr1, tempstr2, tempstr3 : String;
Begin
Base2StringToFGInt('0', zero);
FGIntToBase2String(modb, tempstr1);
modbits := length(tempstr1);
convertBase256to2(P, tempstr1);
tempstr1 := '111' + tempstr1;
j := modbits - 1;
While (length(tempstr1) Mod j) <> 0 Do tempstr1 := '0' + tempstr1;

j := length(tempstr1) Div (modbits - 1);
tempstr2 := '';
For i := 1 To j Do
Begin
tempstr3 := copy(tempstr1, 1, modbits - 1);
While (copy(tempstr3, 1, 1) = '0') And (length(tempstr3) > 1) Do delete(tempstr3, 1, 1);
Base2StringToFGInt(tempstr3, PGInt);
delete(tempstr1, 1, modbits - 1);
If tempstr3 = '0' Then FGIntCopy(zero, temp) Else FGIntMontgomeryModExp(PGInt, exp, modb, temp);
FGIntDestroy(PGInt);
tempstr3 := '';
FGIntToBase2String(temp, tempstr3);
While (length(tempstr3) Mod modbits) <> 0 Do tempstr3 := '0' + tempstr3;
tempstr2 := tempstr2 + tempstr3;
FGIntdestroy(temp);
End;

While (tempstr2[1] = '0') And (length(tempstr2) > 1) Do delete(tempstr2, 1, 1);
ConvertBase2To256(tempstr2, E);
FGIntDestroy(zero);
End;


// Decrypt a string with the RSA algorithm, E^exp mod modb = D
// provide nil for exp.Number if you want a speedup by using the chinese
// remainder theorem, modb = p*q, d_p*e mod (p-1) = 1 and
// d_q*e mod (q-1) where e is the encryption exponent used

Procedure RSADecrypt(E : String; Var exp, modb, d_p, d_q, p, q : TFGInt; Var D : String);
Var
i, j, modbits : longint;
EGInt, temp, temp1, temp2, temp3, ppinvq, qqinvp, zero : TFGInt;
tempstr1, tempstr2, tempstr3 : String;
Begin
Base2StringToFGInt('0', zero);
FGIntToBase2String(modb, tempstr1);
modbits := length(tempstr1);
convertBase256to2(E, tempstr1);
While copy(tempstr1, 1, 1) = '0' Do delete(tempstr1, 1, 1);
While (length(tempstr1) Mod modbits) <> 0 Do tempstr1 := '0' + tempstr1;
If exp.Number = Nil Then
Begin
FGIntModInv(q, p, temp1);
FGIntMul(q, temp1, qqinvp);
FGIntDestroy(temp1);
FGIntModInv(p, q, temp1);
FGIntMul(p, temp1, ppinvq);
FGIntDestroy(temp1);
End;

j := length(tempstr1) Div modbits;
tempstr2 := '';
For i := 1 To j Do
Begin
tempstr3 := copy(tempstr1, 1, modbits);
While (copy(tempstr3, 1, 1) = '0') And (length(tempstr3) > 1) Do delete(tempstr3, 1, 1);
Base2StringToFGInt(tempstr3, EGInt);
delete(tempstr1, 1, modbits);
If tempstr3 = '0' Then FGIntCopy(zero, temp) Else
Begin
If exp.Number <> Nil Then FGIntMontgomeryModExp(EGInt, exp, modb, temp) Else
Begin
FGIntMontgomeryModExp(EGInt, d_p, p, temp1);
FGIntMul(temp1, qqinvp, temp3);
FGIntCopy(temp3, temp1);
FGIntMontgomeryModExp(EGInt, d_q, q, temp2);
FGIntMul(temp2, ppinvq, temp3);
FGIntCopy(temp3, temp2);
FGIntAddMod(temp1, temp2, modb, temp);
FGIntDestroy(temp1);
FGIntDestroy(temp2);
End;
End;
FGIntDestroy(EGInt);
tempstr3 := '';
FGIntToBase2String(temp, tempstr3);
While (length(tempstr3) Mod (modbits - 1)) <> 0 Do tempstr3 := '0' + tempstr3;
tempstr2 := tempstr2 + tempstr3;
FGIntdestroy(temp);
End;

If exp.Number = Nil Then
Begin
FGIntDestroy(ppinvq);
FGIntDestroy(qqinvp);
End;
While (Not (copy(tempstr2, 1, 3) = '111')) And (length(tempstr2) > 3) Do delete(tempstr2, 1, 1);
delete(tempstr2, 1, 3);
ConvertBase2To256(tempstr2, D);
FGIntDestroy(zero);
End;


// Sign strings with the RSA algorithm, M^d mod n = S
// provide nil for exp.Number if you want a speedup by using the chinese
// remainder theorem, n = p*q, dp*e mod (p-1) = 1 and
// dq*e mod (q-1) where e is the encryption exponent used


Procedure RSASign(M : String; Var d, n, dp, dq, p, q : TFGInt; Var S : String);
Var
MGInt, SGInt, temp, temp1, temp2, temp3, ppinvq, qqinvp : TFGInt;
Begin
Base256StringToFGInt(M, MGInt);
If d.Number <> Nil Then FGIntMontgomeryModExp(MGInt, d, n, SGInt) Else
Begin
FGIntModInv(p, q, temp);
FGIntMul(p, temp, ppinvq);
FGIntDestroy(temp);
FGIntModInv(q, p, temp);
FGIntMul(q, temp, qqinvp);
FGIntDestroy(temp);
FGIntMontgomeryModExp(MGInt, dp, p, temp1);
FGIntMul(temp1, qqinvp, temp2);
FGIntCopy(temp2, temp1);
FGIntMontgomeryModExp(MGInt, dq, q, temp2);
FGIntMul(temp2, ppinvq, temp3);
FGIntCopy(temp3, temp2);
FGIntAddMod(temp1, temp2, n, SGInt);
FGIntDestroy(temp1);
FGIntDestroy(temp2);
FGIntDestroy(ppinvq);
FGIntDestroy(qqinvp);
End;
FGIntToBase256String(SGInt, S);
FGIntDestroy(MGInt);
FGIntDestroy(SGInt);
End;


// Verify digitally signed strings with the RSA algorihthm,
// If M = S^e mod n then ok:=true else ok:=false

Procedure RSAVerify(M, S : String; Var e, n : TFGInt; Var valid : boolean);
Var
MGInt, SGInt, temp : TFGInt;
Begin
Base256StringToFGInt(S, SGInt);
Base256StringToFGInt(M, MGInt);
FGIntMod(MGInt, n, temp);
FGIntCopy(temp, MGInt);
FGIntMontgomeryModExp(SGInt, e, n, temp);
FGIntCopy(temp, SGInt);
valid := (FGIntCompareAbs(SGInt, MGInt) = Eq);
FGIntDestroy(SGInt);
FGIntDestroy(MGInt);
End;

End.

我个人不喜欢这个加密算法！速度太慢了……
此外我还有个人修改版本，测试通过了！呵呵：）有意者跟我联系哟
我98年还自己弄了个加密算法，速度比rsa快很多哟，强度也不比rsa差劲哟
，有意者，价格面议哟：））呵呵，只针对商业用户！