文档章节

ElGamal算法进行加密和解密的基本原理及实现

o
 osc_isezqdgg
发布于 2019/09/18 16:33
字数 803
阅读 45
收藏 0

精选30+云产品,助力企业轻松上云!>>>

1、准备步骤

1)取大素数 p 和 g(g < p,g 最好是 p 的素根)

注解:若 g 是素数 p 的一个素根,则 g mod p, g^2 mod p , …, g^p-1 mod p 是 1 到 p - 1 的排列

2)随机选取一整数 x (2 <= x <= (p - 2),(p,g,x) 是私钥)

3)计算 y = g^x (mod p) ( (p,g,y) 是公钥)

 

2、加密过程

1)随机选取一整数 k (2 <= k <= (p - 2) 且 k 与 (p - 1) 互素)

2)计算 a = g^k mod p,b = m*y^k mod p(m 为要加密的明文)

3)密文 C = (a, b)

 

3、解密过程

1)m = b * a^(-x) mod p

注解:b * a^(-x) mod p Ξ m * y^k * g^(-xk) Ξ m * g^(xk) * g^(-xk) Ξ m

 

加密及解密的实现(Java):

import java.util.ArrayList;

public class Main {
    static ArrayList<Integer> suArr = new ArrayList<>();
    public static void main(String[] args) {
        int max = 8096, p, g, x, y, k, a, b, buffer_data;
        char[] m = "abc".toCharArray(); // 加密字符串"abc"
        ArrayList<Integer> C = new ArrayList<>();   // 加密后的密文
        int size1;
        suArr.add(2);

        // 随机取一个小于2048的素数g
        for (int i = 3; i <= 2048; i++) {
            if (isSuShu(i)) suArr.add(i);
        }
        size1 = suArr.size();
        g = getRanNum(size1);

        // 随机取一个大素数p
        for (int i = 2049; i <= max; i++) {
            if (isSuShu(i)) suArr.add(i);
        }
        p = getRanNum(suArr.size() - size1, size1);

        // x的范围是[2,p-2]
        x = (int)(Math.random() * (p-3))+2;
        // k的范围是[2,p-2]且k与p-1互素
        k = (int)(Math.random() * (p-3))+2;
        while (isHuZhi(k, p-1) != 1) {
            k = (int)(Math.random() * (p-3))+2;
        }

        // y = g^x mod p
        y = myPow(g, x, p);

        // a = g^k mod p
        a = myPow(g, k, p);
        C.add(a);

        // 特殊数据test
        // a = 1434;
        // g=1117;
        // k=2403;
        // p=6101;
        // x=714;
        // y=2271;

        // 加密过程,即计算b = m*y^k mod p (m是明文)
        for (char c : m) {
            C.add((int)c*myPow(y, k, p) % p);
        }

        buffer_data = myPow(a, x, p);
        buffer_data = exGcd(buffer_data, p)[0]; // 求(a^x)^(-1) mod p等价于求a^(-x) mod p
        if (buffer_data < 0) buffer_data += p;

        // 将解密后的明文输出
        for (int i = 1; i < C.size(); i++) {
            System.out.print((char)(C.get(i) * buffer_data % p));
        }
    }

    // 判断一个数是否为素数
    public static boolean isSuShu(int num) {
        int max = (int) Math.sqrt(num);
        for (int i = 2; i <= max; i++) {
            if (num % i == 0)
                return false;
        }
        return true;
    }

    // 在素数数组中随机取一个数
    public static int getRanNum(int size) {
        return suArr.get((int) (Math.random() * (size)));
    }

    // 在素数数组中的(left, arr.size())之间随机取一个数
    public static int getRanNum(int size, int left) {
        return suArr.get((int) (Math.random() * (size)) + left);
    }

    // 判断两个数是否互质
    public static int isHuZhi(int a, int b) {
        return b == 0 ? a : isHuZhi(b, a % b);
    }

    public static int myPow(int a, int b, int m) {
        int res = 1;
        a %= m;
        while (b != 0) {
            if ((b & 1) == 1)
                res = (res * a) % m;
            a = (a * a) % m;
            b >>= 1;
        }
        return res;
    }

    public static int getSuGen(int p) {
        boolean isSuGen;
        for (int g : suArr) {
            isSuGen = true;
            for (int i = 1; i < p; i++) {
                if (myPow(g, i, p) != i) isSuGen = false;
            }
            if (isSuGen) return g;
        }
        return 2; // 如果在素数数组中找不到p的素根,则返回一个默认值
    }

    // 扩展欧几里得算法求a模b的逆元
    public static int[] exGcd(int a, int b) {
        if (b == 0) {
            int[] arr = new int[]{1, 0};
            return arr;
        } else {
            int[] arr = exGcd(b, a % b);
            int x = arr[0];
            arr[0] = arr[1];
            arr[1] = x - (a / b) * arr[1];
            return arr;
        }
    }
}

/*
 * 参考:
 * 素根的定义:a是素数p 的一个素根,如果a mod p, a^2 mod p , …, a^p-1 mod p 是1到p-1的排列,称a是P的一个素根
 * 加密时x和k的选取:https://blog.csdn.net/qq_34490018/article/details/79758620
 */

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
非对称加密算法-ElGamal算法

一、概述 1、ElGamal算法和ECC算法基于离散对数问题 2、这个是一个单向的过程。虽然密钥对构造简单,但是只是乙方向另外一方单向传送数据进行加解密,不能反向操作 3、这里只有“公钥加密、私...

王爵nice
2015/03/31
123
0
高等数据加密——非对称加密算法

对称加密算法仅有一个密钥,既可用于加密,亦可用于解密。而非对称加密算法拥有两个密钥,一个用于加密,另一个则用于解密。相比对称加密算法的单钥体系,非对称加密算法的双钥体系更为安全。...

blackfoxMa
2019/04/19
4
0
公钥密码体制的研究与发展的基本理解

Abstract:文中对于公钥密码体制的研究与发展进行了介绍,其中着重介绍了几个比较常用的公钥密码体制RSA,EIGamal Keywords: 公钥密码体制,RSA,离散对数问题 1. 引言 公钥密码体制又称公开密...

osc_y8z1vlz9
2018/03/31
1
0
java加密种类

种类: Base64加密;base64加密其实不属于加密的范畴,只是用于转码,比如URL的转码。 消息摘要算法;其中包含MD5,SHA,MAC加密,都是不可逆的,但是网上有些说可以解密。 对称加密算法;何...

osc_o401d1ng
2018/04/16
1
0
加密算法的分类:不可逆,可逆,对称式,非对称

加密算法的分类 1)不可逆加密算法 2)可逆加密算法 可逆加密算法又分为两大类:“对称式”和“非对称式”。 非对称加密算法与对称加密算法的区别 首先,用于消息解密的密钥值与用于消息加密...

飞龙栖息地
2013/08/22
2.9K
0

没有更多内容

加载失败,请刷新页面

加载更多

Mysql 通过binlog日志恢复数据

Binlog日志,即binary log,是二进制日志文件,有两个作用,一个是增量备份,另一个是主从复制,即主节点维护一个binlog日志文件,从节点从binlog中同步数据,也可以通过binlog日志来恢复数据...

osc_lduvstkg
45分钟前
18
0
前端js日期时间格式转换

前端前后端接口处理时经常会遇到需要转换不同时间格式的情况,比如时间戳格式转换成正常日期显示来进行前端展示。 下面是分享一些不同格式的日期转换函数方法。 /** * 时间戳转时间 * @param...

osc_gccs85s0
47分钟前
9
0
微服务中如何设计一个权限授权服务

基于角色的访问控制 (RBAC)   是将系统访问限制为授权用户的一种方法,是围绕角色和特权定义的与策略无关的访问控制机制,RBAC的组件使执行用户分配变得很简单。   在组织内部,将为各种...

osc_ie20bwji
49分钟前
12
0
前端js日期时间格式转换

前端前后端接口处理时经常会遇到需要转换不同时间格式的情况,比如时间戳格式转换成正常日期显示来进行前端展示。 下面是分享一些不同格式的日期转换函数方法。 /** * 时间戳转时间 * @param...

osc_sqfqhs81
50分钟前
38
0
(转)【D3D11游戏编程】学习笔记三:XNAMath之XMMATRIX

(注:【D3D11游戏编程】学习笔记系列由CSDN作者BonChoix所写,转载请注明出处:http://blog.csdn.net/BonChoix,谢谢~) 在熟悉了XMVECTOR的风格及规则之后,再来了XNA数学库中的矩阵就容易...

osc_yumj26qz
52分钟前
32
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部