算法练习(7):欧几里得算法的应用：RSA的加密解密

本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论

算法(第4版)

知识点

• 公钥
• 私钥
• 欧拉定理
• 欧几里得算法
• 模反元素
• RSA加密

我们已经做了一些算法习题了，这次的文章就不讲新的算法了，而是讲算法的一个实际使用：欧几里得算法。
在算法练习(4):二分法查找中我们已经介绍了欧几里得算法，并使用欧几里得算法计算了两个整数的最大公约数。

RSA算法是计算机世界最重要的算法，它是计算机通信安全的基石,因为任何用到加解密的地方都会用到RSA算法。它的原理就是通过两个互质的数来分别作为公钥和私钥(暂时这么理解)加解密实现。

Java的实现如下：

//例子为算47 * x + 30 * y ==1 的解
public class Exercise
{
    public static void main(String[] args)
    {
        int[] p = new int[2];
        int a = 47;
        int b = 30;
        RSA(a,b,p);
        System.out.print("p[0] is: " + p[0] + ";p[1] is：" + p[1]);//p1为私钥
    }
    public static  int[] RSA(int a,int b,int[] p)//这里假设a > b
    {
        if(a%b == 1)
        {
            p[0] = 1;
            p[1] = -(a - 1) / b;
            return p;
        }
            else
        {
                RSA(b,a % b,p);
                int t = p[0];
                p[0] = p[1];
                p[1] = t - (a / b) * p[1]; 
                return p;
        }
    }
}

广告

我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。