实现椭圆曲线上离散对数问题的求解_椭圆离散-程序员宅基地

密码学实验课的题目，分享一下自己的代码，可能不够完美，供参考~自己动手才是王道哦！

一、实验目的

掌握椭圆曲线上的加法定律；
熟练求解椭圆曲线上的离散对数问题。

二、实验原理

（1）有限域GF§上的椭圆曲线：对于固定的a和b，满足形如方程
y2≡x3+ax+b(mod p) ( a,b,x,yGF§且4a3+27b2(mod p)≠0).
（2）椭圆曲线Ep(a,b)上的加法定义如下：
设P, Q, REp(a,b)，则
①P+O=O+P=P；
②若P=(x,y)，那么(x, y)+(x, -y)=O，即(x, -y)是P的加法逆元，记为-P；
③P+Q=Q+P；
④(P+Q)+R=P+(Q+R)；
⑤设P=(x1,y1)，Q=(x2,y2)，P≠-Q，则P+Q=(x3,y3)由以下确定：
x3≡λ2－x1－x2(mod p)
y3≡λ(x1－x3)－y1(mod p)
其中。
（3）椭圆曲线上的离散对数问题（ECDLP）：
用E(GF§)表示定义在有限域GF§上椭圆曲线E的有理子群，设任意两点P，QE (GF§)。求使kP=Q成立的k值问题就是E上的椭圆曲线离散对数问题。

三、实验要求

编程求解椭圆曲线上的离散对数问题，主要包括椭圆曲线上的加法函数，乘法逆元的求解，以及验证点是否在椭圆曲线上等。

四、实验内容

GF(29)上曲线E：y2=x3+4x+20 (mod p)；E上两点P=(13,23)，Q=(3,28)。编程求解k使满足kP=Q。

五、源代码

// 密码学08.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
using  namespace std;
int qx ;
int qy ;

class Point{
public:
	Point(int a, int b):px(a),py(b){}
	int getx(){ return px; }
	int gety(){ return py; }
	Point add(Point p2);
private:
	int px, py;
};

int x, y, q;
int func(int a, int  b){
	if (b == 0){
		x = 1; y = 0; q = a;
	}
	else{
		func(b, a%b);
		double t = x;
		x = y; y = t - a / b*y;
	}
	return y;//y是 b mod a的逆元 不保证y在一定范围内
}
Point Point:: add(Point p2){
	int x1 = px;
	int y1 = py;
	int x2 = p2.getx();
	int y2 = p2.gety();
	int r = 0;
	int x3 = x1, y3 = y1;
		if (x1 == x2&&y1 == y2){
			int ni = func(29, 2 * y1);
			while (ni<0){
				ni += 29;
			}
			r = ((3 * x1*x1 + 4)*ni)%29;
		}
		else{
			int x21 = x2 - x1;
			while (x21 < 0){ x21 = x21 + 29; }
			int ni = func(29, x21);
			while (ni<0){
				ni += 29;
			}
			r = ((y2 - y1)*ni)%29;
		}
    x3 = (r*r - x1 - x2);
	while (x3 < 0 || x3 >= 29){
		if (x3 < 0){ x3 = x3 + 29; }
		else{ x3 = x3 - 29; }
	}
    y3 = (r*(x1 - x3) - y1);
	while (y3< 0 || y3 >= 29){
		if (y3 < 0){y3 = y3 + 29; }
		else{ y3= y3 - 29; }
	}
	return Point(x3, y3);

}
int qiuk(){
	Point p(13, 23);
	Point pp = p;
	for (int i = 0;; i++){
		if (pp.getx() == 3 && pp.gety() == 28){
			return (i + 1);
		}
		pp = pp.add(p);
	}
}
int _tmain(int argc, _TCHAR* argv[])
{
	cout << "曲线E：y2=x3+4x+20 (mod 29)" << endl;
	cout << "点P=(13,23)，Q=(3,28)" << endl;
	cout << "满足kP=Q的k是：" << endl;
	cout <<qiuk()<<endl;
	return 0;
}

在这里插入图片描述

本文链接：https://blog.csdn.net/weixin_42189863/article/details/86490100

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Android Studio 导入安卓源码步骤_怎么导入别人的android源码-程序员宅基地

文章浏览阅读1.4w次，点赞14次，收藏68次。前言我们做Android系统源码开发，在定位问题的过程中经常要从App层跟踪代码到Framework层中，为了更加方便的查找代码，这时候就需要把整个工程源码导入到Android Studio中，导入后我们也可以通过断点调试，更加快速和准确地定位分析解决问题。操作步骤开发环境： Ubantu 20.4 Android Studio4.2 Android 11(R) 源码步骤一 1. 进入源码根目录，初始化系统环..............._怎么导入别人的android源码

bmp转十六进制hex样例_bmp图片转成hex-程序员宅基地

文章浏览阅读2.8k次。// $ xxd -i logo.bmp logo.h#include //TO_DO ++++++++unsigned char logo_bmp[] = { 0x42, 0x4d, 0xde, 0xc9, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x36, 0x00, 0x00, 0x00, 0x28, 0x00, 0x00, 0x0_bmp图片转成hex

欲望你真的清楚么？-程序员宅基地

文章浏览阅读837次。一、问题何为欲望？二、何为欲望欲望（Desire）是由生物的本性产生的想达到某种目的的要求，欲望无善恶之分，关键在于如何控制。欲望是世界上所有动物最原始的、最基本的一种本能。从人的角度讲是心理到身体的一种渴望、满足，它是一切动物存在必不可少的需求。一切动物最基本的欲望就是生存与存在。简单的来说就是爱与不满足。 ...

基于微信小程序和SSM的校园二手交易小程序源码+论文+答辩PPT+开题报告+任务书_基于springboot的校园二手商城交易微信小程序开题答辩问题-程序员宅基地

文章浏览阅读269次。二手平台后台功能主要包括：管理员登陆、管理员管理、APP用户管理、留言评论管理、商品管理、商品发布等功能。1.在数据库设计方面，数据表是系统实现的一个难点，用户登录如何区分管理员还是普通用户，多个物品的种类价格处理，这些在数据库的设计上都是需要仔细考虑的；后端：Java+SSM。_基于springboot的校园二手商城交易微信小程序开题答辩问题

Avue-crud常用配置项_avue dicurl 带参数-程序员宅基地

文章浏览阅读2k次，点赞4次，收藏6次。avue的一些配置1.表格option配置项<avue-crud :option="option" ref="crud" //表格常用事件 @on-load="getList"//这个事件会在表格所在的组件加载时就会执行后面的getList方法，初始化表格数据。并且当表格翻页或者pageSize变化时候也会自动执行该方法，这时候表格绑定的 :page.sync="page"中的page的值也会随时更新，当页面大小变化时，还会自己将页面变为1 如果使用了这个方法其实表格的_avue dicurl 带参数

Xcode12.5及以上安装MonkeyDev后无法编译CommandTool项目解决办法_file /applications/xcode.app/contents/plugins/idei-程序员宅基地

文章浏览阅读1.7k次。环境: MacOSX 11.5.2(intel) , Xcode 12.5.1Xcode 12.5.1 正常安装完成MonekeyDev后，能看到MonkeyDev的项目，但是Command Tool类型的项目无法编译，编译时报错:Showing Recent Messages unable to resolve product type 'com.apple.product-type.tool' for platform 'iphoneos'解决办法:使用记事本编辑: /Applicat_file /applications/xcode.app/contents/plugins/ideiossupportcore.ideplugin/co