golang 实现 RSA 的加密解密(2)-木庄网络博客

最后的 d 就是算出来的 d.

整个过程使用递归的思想可以很好地计算出最后的 d

实现

// @author 我的我的// @date // @desc rsa 算法的简单实现package mainimport ("fmt""math")type (// 64 位 平台 64 位// 整 64 位以上长度的需要自己实现了, 参考 IEEE[triple E]754PublicKey struct {
        E int}
    
    PrivateKey struct {
        D int}
    
    MiniRSA struct {
        PublicKey  PublicKey  `json:"public_key"`PrivateKey PrivateKey `json:"-"`N          int        `json:"n"`}
)func main() {var p, q, e, x, y int = 47, 71, 79, 0, 0// 判断 p q 是否为素数if !(isPrime(p) && isPrime(q)) {panic(fmt.Sprintf("isPrime(%d) = %v and isPrime(%d) = %v need isPrime", p, isPrime(p), q, isPrime(q)))
    }
    N := p * q
    setaN := (p - 1) * (q - 1)if gcd(e, setaN) > 1 || N < e {panic("e 要 与 setaN 互质 并且小于 N")
    }
    extGCD(e, setaN, &x, &y)// 得出公钥和私钥miniRSA := MiniRSA{PrivateKey: PrivateKey{D: x}, PublicKey: PublicKey{E: e}, N: N}
    
    fmt.Printf("miniRSA %#v\n", miniRSA)
    plainText := 2020cipherText := enc(plainText, miniRSA.PublicKey.E, miniRSA.N)
    fmt.Println("明文:", plainText, "\t密文: ", cipherText, "\t解密:", dec(cipherText, miniRSA.PrivateKey.D, miniRSA.N))
    
    plainText = 233cipherText = enc(plainText, miniRSA.PublicKey.E, miniRSA.N)
    fmt.Println("明文:", plainText, "\t密文: ", cipherText, "\t解密:", dec(cipherText, miniRSA.PrivateKey.D, miniRSA.N))
    
}// 求最大公约数func gcd(a, b int) int {if a == 0 || b == 0 {return 0}// 直到 a == b 为止for a != b {if a > b {
            a -= b
        } else {
            b -= a
        }
    }return a
}// 拓展的欧几里得算法func extGCD(a, b int, x, y *int) int {if b == 0 {
        *x = 1*y = 0return a
    }
    d := extGCD(b, a%b, x, y)
    *x, *y = *y, *x-a/b*(*y)return d
}// 判断素数func isPrime(prime int) bool {// 1 不是素数flag := truefor i := 2; i <= int(math.Sqrt(float64(prime))); i++ {if prime%i == 0 {
            fmt.Println(prime, i)
            flag = falsebreak}
    }return flag
}// 使用公钥加密func enc(plainText int, e, n int) int {return powMod(plainText, e, n)
}// 使用私钥来解密func dec(cipherText int, d, n int) int {return powMod(cipherText, d, n)
}// 快速幂问题func quickPow(a, b int) int {// 不考虑小于零if b == 0 {return 1}
    ans := quickPow(a, b/2)
    ans *= ansif b%2 == 1 {
        ans *= a
    }return ans
    
}// 同余func powMod(a, n, m int) int {// 不考虑小于零if n == 0 {return 1}
    
    x := powMod(a, n/2, m)
    ans := x * x % mif n%2 == 1 {
        ans = ans * a % m
    }return ans
}// end 复制代码