*******************RSA算法示例************************
*公开密钥 n:两个素数p和q的乘积
* e: 与(p-1)(q-1)互素
*
*私人密钥 d: e的负一次方((mod(p-1)(q-1)))
*加密 c=m的e次方 mod n
*解密 m=c的d次方 mod n
******************************************************
* p=47 q=71
* n=3337 （公钥）
* e=79 （公钥）
* d=1019 (私钥）
* m=688 (原始数据)
* c=1570 (加密后的数)
******************************************************
*例 p=47 q=71
*则 n=pq=3337
*
*加密密钥e与(p-1)(q-1)=46*70=3220没有公因子
*随机选取e，如79,那么
* d=79的负一次方 mod 3220=1019
* 设要加密的数为 m=688
*
*加密 c=m的e次方 mod n
* =688的79次方 mod 3337
* =1570
*解密 m=c的d次方 mod n
* =1570的1019次方 mod 3337
* =688
*******************************************************
CLEAR
*?encrypt_decrypt1(688,79,3337)
aa=3330
?\"加密前：\",aa
xx=encrypt_decrypt2(aa,65537,68714299)
?\"加密结果：\",xx
?\"还原：\",encrypt_decrypt2(xx,48843233,68714299)
?encrypt_decrypt1(1570,1019,3337)
?
?encrypt_decrypt2(688,79,3337)
?encrypt_decrypt2(1570,1019,3337)
********************************************************
*一般情况下，n和e都能够跟踪到，需要对n进行质数分解
*如 107031778601497 或 9992607623773123
?\"n=9992607623773123\"
?\"经分解质因数:\"
?\"p:\"
?decrypt(9992607623773123) &&结果为99999677
?\"q:\"
?9992607623773123/decrypt(9992607623773123) &&结果为99926399
*以上两个数就是传说中的p和q
*这里设e=17,它与n是互为素数的，也就是常用的(3,17,65537(即2的16次方+1))几个值
*下面需要计算d,如上例中的:
* p=47 q=71
* n=3337 （公钥）
* e=79 （公钥）
*计算方法是(d * e ) mod ((p-1)(q-1)) 的余数为1
?Dekey(47,71,79)
*********************************************************
*下面这个两个函数都可以计算(m ^ e) mod n
********************************************************
*降价法
********************************************************
PROCEDURE encrypt_decrypt1
LPARAMETERS m, e, n
LOCAL a,b,c
a=m
b=e
c=1
do while b<>0
IF b%2==0
b = b / 2 &&降阶
a = (a * a) % n
ELSE
b = b - 1
c = (a * c) % n
ENDIF
ENDDO
RETURN c
ENDPROC
**********************************************************[Page]
PROCEDURE encrypt_decrypt2
LPARAMETERS m,e,n
PRIVATE intFlag, intResult
intResult = 1
FOR intFlag = 1 TO e
intResult = (intResult * m) % n
ENDFOR
RETURN intResult
ENDPROC
*********************************************************
*穷举分解质数
********************************************************
PROCEDURE DeCrypt
LPARAMETERS nNum
LOCAL nStr,nLen,nStart,nEnd,nReturn
nStr=STR(nNum,16) &&VFP中只能处理16位数
nLen=LEN(ALLTRIM(nStr)) &&取得公钥长度
*以下计算起始的质数 最大的质因数为素数的一半长度
nStart=INT(nLen/2)
IF MOD(nLen,2)<>0
nStart=nStart+1
ENDIF
cStr=REPLICATE(\"9\",nStart)
nEnd=VAL(REPLICATE(\"9\",nStart-1))
FOR nReturn=VAL(cStr) to nEnd step -1
IF MOD(nNum,nReturn)=0
EXIT
ENDIF
ENDFOR
RETURN nReturn
ENDPROC
************************************************
*穷举计算私钥d
*(d * e ) mod ((p-1)(q-1)) 的余数为1
***********************************************
PROCEDURE DeKey
LPARAMETERS p,q,e
LOCAL z,x
z=(p-1)*(q-1)
FOR x=1 to z
IF (x*e)%z=1
RETURN x
ENDIF
ENDFOR
ENDPROC
最新评论