【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】

这篇具有很好参考价值的文章主要介绍了【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

实验二、数论基础(中)

一、实验内容

1、扩展欧几里得算法(Extended Euclid’s Algorithm)

(1)、算法原理

已知整数 a , b ,扩展的欧几里得算法可以在求得 a , b最大公约数的同时,找到一对整数 x , y ,使得 a , b , x , y 满足如下等式:ax + by = d = gcd(a,b), 其中 gcd(a, b)ab 的最大公约数。

(2)、算法流程

本算法的大致流程如下图所示:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

(3)、 算法的代码实现(C语言)

# include <stdio.h>

int r2, s2, t2;

void Extended_Euclid(int a, int b);

int main(){
    int a, b;
	printf("请输入整数a:\n");
	scanf("%d", &a);
	printf("请输入整数b:\n");
	scanf("%d", &b);
	Extended_Euclid(a, b);
	printf("a和b的最大公因子为: %d\n", r2);
	printf("满足ax + by = gcd(a, b)的因子x和y分别为: %d %d\n", s2, t2);
	return 0;
}
	
void Extended_Euclid(int a, int b){
    int r, s, t;
	int r1, s1, t1;
	int tmp1, tmp2, tmp3;
	int q;
	r = a;
	s = 1;
	t = 0;
	r1 = b;
	s1 = 0;
	t1 = 1;
	while(r1 != 0){
	    q = r / r1;
		tmp1 = r - q * r1;
		tmp2 = s - q * s1;
		tmp3 = t - q * t1;
		r = r1;
		s = s1;
		t = t1;
		r1 = tmp1;
		s1 = tmp2;
		t1 = tmp3;
	}
	r2 = r;
	s2 = s;
	t2 = t;
	return;
}

(4)、算法测试

测试点1:a = 7, b = 5

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

测试点2:a = 31, b = -13

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

测试点3:a = 24, b = 36

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

(5)、一点思考

线性系数x和y不是唯一的,比如样例3中既可以是24 * (-1) + 36 * 1 = 12,也可以是24 * 2 + 36 * (-1) = 12. 如何能使算法找出所有满足条件的解?

2、简单幂取模算法(Simple Exponentiation-Module Algorithm)

(1)、算法原理

每次做乘法操作时都取模,即“乘一次模一次,循环往复”。数学表达式为 d = (((x^(n-1))mod m)*x) mod m

(2)、算法流程

本算法的大致流程如下图所示:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

(3)、算法的代码实现(C语言)

#include <stdio.h>


int main(){
	int x, n, m;
	int ans;
	int i;

    printf("请输入底数x的值:\n");
	scanf_s("%d", &x);

    printf("请输入指数n的值:\n");
    scanf_s("%d", &n);

    printf("请输入模数m的值:\n");
    scanf_s("%d", &m);

	ans = 1;
	
	for(i = 1;i <= n;i ++)
    {
		ans = (ans * x) % m;
	}
	
	printf("%d", ans);
	
	return 0;
}

(4)、算法测试

测试点1:x = 7, n = 16, m = 3

运行时截图:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

测试点2:x = 5, n = 1003, m = 31

运行时截图:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java
2、快速幂取模算法(Fast Exponentiation-Module Algorithm)

(1)、算法原理

常规的幂取模算法包含过多的乘法以及取模运算,计算步骤多,导致算法的效率很低。根据模运算和幂运算的性质,可以将幂次(指数n)用2进制进行表示,然后再迭代进行求模幂,从而减少乘法和取模的次数。

(2)、算法流程

本算法的大致流程如下图所示:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

(3)、算法的代码实现(C语言)

#include <stdio.h>


int main()
{
	int x, n, m;
	
	int d = 1;
	
	printf("请输入底数x的值:\n");
	scanf_s("%d", &x);
	
	printf("请输入指数n的值:\n");
	scanf_s("%d", &n);
	
	printf("请输入模数m的值:\n");
	scanf_s("%d", &m);
	
	while(n > 0)
	{
		if((n % 2) == 1)
		{
			d = (d * x) % m;
			n = (n - 1) / 2;
		}
		else
		{
			n = n / 2;
		}
		x = (x * x) % m;
	}
	
	printf("快速幂取模计算结果:\n");
	printf("%d", d);
	
	return 0;
}

(4)、算法测试
测试点1:x = 7, n = 16, m = 3

运行时截图:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java测试点2:x = 5, n = 1003, m = 31

运行时截图:

【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】,C语言,Java,密码学,密码学,c语言,java

二、参考文献

1、《密码编码学与网络安全——原理与实践(第七版)》(Cryptography and Network Security, Principles and Practice, Seventh Edition),【美】威廉 斯托林斯 William Stallings 著,王后珍等 译,北京,电子工业出版社,2017年12月。

2、《密码学实验教程》,郭华 刘建伟等 主编,北京,电子工业出版社,2021年1月。文章来源地址https://www.toymoban.com/news/detail-789931.html

到了这里,关于【网络安全】【密码学】【北京航空航天大学】实验二、数论基础(中)【C语言和Java实现】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【北京航空航天大学】【信息网络安全实验】【实验一、密码学:DES+RSA+MD5编程实验】

    1. 通过对DES算法的代码编写,了解分组密码算法的设计思想和分组密码算法工作模式; 2. 掌握RSA算法的基本原理以及素数判定中的Rabin-Miller测试原理、Montgomery快速模乘(模幂)算法,了解公钥加密体制的优缺点及其常见应用方式; 3. 掌握MD5算法的基本原理,了解其主要应用

    2024年02月19日
    浏览(52)
  • 网络安全密码学

    目录 一 古代密码学 1.替换法 2.移位法 3.古典密码学的破解方式 二 近代密码学 三 现代密码学 1.散列函数(哈希函数) 2.对称加密 3.非对称加密 四 如何设置密码才安全 1.密码不要太常见 2.各个应用软件里面的密码不要设置一样 3.在设置密码的时候,可以加一些特殊的标记 实

    2023年04月12日
    浏览(50)
  • 网络安全之密码学

    目录 密码学 定义 密码的分类 对称加密 非对称加密 对称算法与非对称算法的优缺点 最佳解决办法 --- 用非对称加密算法加密对称加密算法的密钥 非对称加密如何解决对称加密的困境 密钥传输风险 密码管理难 常见算法 对称算法 非对称算法 完整性与身份认证最佳解决方案

    2024年02月01日
    浏览(77)
  • 网络安全与密码学

    1、网络安全威胁 破坏网络安全的一些理论方式: 窃听:窃听信息,在网路通信双方直接进行窃听。 插入:主动在网络连接中插入信息(可以在message中插入恶意信息) 假冒:伪造(spoof)分组中的源地址,假冒客户端或服务器。 劫持:通过移除/取代发送方发或接收方“接管

    2024年02月16日
    浏览(46)
  • 网络安全:密码学基本理论.

    密码学是研究编制密码和破译密码的技术科学。研究密码变化的客观规律,应用于编制密码以保守通信秘密的,称为编码学;应用于破译密码以获取通信情报的,称为破译学,总称密码学. 目录 网络安全:密码学基本理论. 密码学基本概念: 密码安全性分析: 密码体系分析:

    2024年02月16日
    浏览(38)
  • 【网络安全】1.4 密码学基础

    密码学是网络安全的核心组成部分,它帮助我们保护信息,防止未经授权的访问。在这篇文章中,我们将从基础开始,深入了解密码学的基本概念和原理,包括加密、解密、密钥、哈希函数等。我们将尽可能使用简单的语言和实例,以便于初学者理解。 密码学是一门研究信息

    2024年02月07日
    浏览(44)
  • 计算机网络安全——密码学入门

            网络安全是指在网络领域、专业领域的网络安全包括在基础计算机网络基础设施中所做的规定,网络管理员采取的策略来保护网络及网络可访问资源免受未经授权的访问,以及对其有效性(或缺乏)的持续不断的监控和测量的结合。 1.1.1 保密性         只有授

    2024年01月19日
    浏览(53)
  • 密码学的社会网络:如何保护社交网络的安全

    社交网络已经成为了现代人们生活中不可或缺的一部分,它们为我们提供了一种与家人、朋友和同事保持联系的方式。然而,这种联系也带来了一些挑战,因为社交网络上的数据经常被盗、篡改或泄露。因此,保护社交网络的安全至关重要。 在这篇文章中,我们将探讨密码学

    2024年02月20日
    浏览(64)
  • 《计算机系统与网络安全》 第四章 密码学基础

    🌷🍁 博主 libin9iOak带您 Go to New World.✨🍁 🦄 个人主页——libin9iOak的博客🎐 🐳 《面试题大全》 文章图文并茂🦕生动形象🦖简单易学!欢迎大家来踩踩~🌺 🌊 《IDEA开发秘籍》学会IDEA常用操作,工作效率翻倍~💐 🪁🍁 希望本文能够给您带来一定的帮助🌸文章粗浅,敬

    2024年02月11日
    浏览(50)
  • 【网络与信息安全学报】区块链密码学隐私保护技术综述——CCF T2

    区块链密码学隐私保护技术综述 Survey on blockchain privacy protection techniques in cryptography Abstract 近年来,数据隐私问题日益明显,如何在区块链中实现有效的隐私保护是研究热点。针对区块链在隐私保护上的研究现状与发展态势,阐述了区块链在交易地址、预言机以及智能合约上

    2024年02月03日
    浏览(66)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包