python 代码说明 RAS基本原理

import gmpy2

q = 7
p = 11
e = 13
m = 71
if __name__ == '__main__':
    print('step 0 公钥和私钥')
    print('     公钥（n，e)')
    print('     私钥（n，d)')

    # step 1
    n = p * q
    print(f'\nstep 1 最大公约数')
    print(f'    随机质数:p: {p}')
    print(f'    随机质数:q: {q}')
    print(f'    选择一个与φ(n)互质的整数e,e任意选取一个大整数e，满足 gcd(e, φ(n))=1 所有大于p和q的素数都可用 e: 13')
    print(f'    质数之和(最大公约数):n=pq = (7 * 11) = {n}')
    print(f'    公钥（n，e) => （77，13) ')

    # step 2
    phi = (q - 1) * (p - 1)
    print(f'\nstep 2  ( n ) 的欧拉函数')
    print(f'    φ(n)=(p-1)(q-1) => ({p}-1)({q}-1)  = {phi} ')

    # step 3
    d = gmpy2.invert(e, phi)
    print(f'\nstep 3 私钥（n，d) d 的计算:  d计算')
    print(f' (de) mod φ(n) = 1 : d*13 mod 60 = 1  => d*13 ≡ 1 (mod 60)  =>d= {d}  ')
    print(f'  v（n，d) => （77，37)  d 私密保存')

    # step 4
    c = pow(m, e, n)
    print(f'\nstep 4 明文公钥加密成密文')
    print(f' m：明文 {m}   公钥（n，e) => （77，13) ')
    print(f' c：密文  c = m^e mod n  => {m} ^ {e} mod {n}  => {c} ')

    # step 5
    m = pow(c, d, n)
    print(f'\nstep 4 私钥解密密文成明文')
    print(f' c：密文 {c}    私钥（n，d) => (77，37)')
    print(f' c：明文  m = c^d mod n  => {c} ^ {d} mod {n}  => {m} ')

    print('RSA 核心原路：欧拉定理，模运算与指数运算之间的关系')
    print('RSA 安全性：依赖于大整数分解的难度')
    print('RSA 缺点： RSA 算法涉及大数运算，包括大素数生成、模幂运算等。 计算非常耗时，随着密钥长度增加计算开销会进一步增加')