RSAImpl.mesa
DIRECTORY
BigCardinals,
RSA;
RSAImpl:
CEDAR
PROGRAM
IMPORTS BigCardinals
EXPORTS RSA =
BEGIN OPEN BigCardinals;
ConditionedPrime:
PROC [length:
CARDINAL]
RETURNS [prime: BigCARD, c1, c2:
CARDINAL ← 0] ~ {
one: BigCARD ← BigFromSmall[1];
two: BigCARD ← BigFromSmall[2];
three: BigCARD ← BigFromSmall[3];
largeModThree, factorModThree, adjust: INTEGER;
large: BigCARD ← BigRandom[2*length/3 + 1];
factor: BigCARD ← BigRandom[length/3];
IF NOT BigOdd[large] THEN large ← BigAdd[large, one];
UNTIL BigPrimeTest[large]
DO
large ← BigAdd[large, two];
c1 ← c1 + 1;
ENDLOOP;
largeModThree ← BigToSmall[BigDivMod[large, three].rem];
IF BigOdd[factor] THEN factor ← BigAdd[factor, one];
factorModThree ← BigToSmall[BigDivMod[factor, three].rem];
adjust ← (2*(factorModThree - largeModThree) + 6) MOD 6;
factor ← BigAdd[factor, BigFromSmall[adjust] ];
prime ← BigAdd[BigMultiply[large, factor], one];
large ← BigMultiply[large, BigFromSmall[6] ];
UNTIL BigPrimeTest[prime]
DO
prime ← BigAdd[prime, large];
c2 ← c2 + 1;
ENDLOOP;
};
KeyGenerate:
PUBLIC
PROC [length:
CARDINAL]
RETURNS [public, private: BigCARD, pc1, pc2, qc1, qc2:
CARDINAL] ~ {
one: BigCARD ← BigFromSmall[1]; three: BigCARD ← BigFromSmall[3];
p, q: BigCARD;
[p, pc1, pc2] ← ConditionedPrime[2*length/5 + 1];
[q, qc1, qc2] ← ConditionedPrime[3*length/5];
public ← BigMultiply[p, q];
private ← BigInverse[three, BigMultiply[BigSubtract[p, one], BigSubtract[q, one]]];
};
Encrypt:
PUBLIC
PROC [plain, public: BigCARD]
RETURNS [encrypted: BigCARD] ~ {
encrypted ← BigExponentiate[plain, BigFromSmall[3], public] };
Decrypt:
PUBLIC
PROC [encrypted, public, private: BigCARD]
RETURNS [plain: BigCARD] ~ {
plain ← BigExponentiate[encrypted, private, public] };
Test: PROC [iterations: CARDINAL] RETURNS [BOOLEAN] ~ {
prime, message, public, private, coded, uncoded: BigCARD;
pc1, pc2, qc1, qc2:
CARDINAL;
THROUGH [0..iterations)
DO
[prime, pc1, pc2] ← ConditionedPrime[3];
IF BigZero[BigDivMod[BigSubtract[prime,
BigFromSmall[1]],BigFromSmall[3]].rem] THEN ERROR;
message ← BigRandom[4];
[public, private, pc1, pc2, qc1, qc2] ← KeyGenerate[5];
coded ← Encrypt[message,public];
uncoded ← Decrypt[coded,public,private];
IF NOT BigCompare[message, uncoded] = bigEqual THEN ERROR
ENDLOOP;
RETURN[TRUE];
};
Stats:
PROC [iterations:
CARDINAL]
RETURNS [tc1, tc2:
LONG
CARDINAL ← 0] ~ {
prime: BigCARD;
c1, c2: CARDINAL;
THROUGH [0..iterations)
DO
[prime, c1, c2] ← ConditionedPrime[25];
tc1 ← tc1 + c1; tc2 ← tc2 + c2;
ENDLOOP;
};
END.
--Test Data
&depth ← 7
&keys ← rsaimpl.KeyGenerate[25]
&message ← BigCardinalsImpl.BigRandom[24]
&coded ← rsaimpl.Encrypt[&message,&keys.public]
&uncoded ← rsaimpl.Decrypt[&coded,&keys.public,&keys.private]