密码学基础——GF(2)有限域上的矩阵求逆

这篇具有很好参考价值的文章主要介绍了密码学基础——GF(2)有限域上的矩阵求逆。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

上篇文章介绍了实数域上的线性代数求解可逆矩阵的方法,但有时候我们有更复杂的需求,如在有限域上求解可逆矩阵,有限域是一个很有意思的东西,它的知识可见这篇文章
今天我们简单描述如何在GF(2)有限域上求解4X4矩阵的可逆矩阵。密码学基础——GF(2)有限域上的矩阵求逆

数据结构

总所周知,GF(2)上的加法和乘法可以分别用异或(^)和逻辑与(&)来表示,因此,我们可以将矩阵中的每一行都可以被定义为一个数字,而不是一个二进制数组。这样做除了内存成本外,运行也会更高效。因为行上的操作比列上的操作更快,例如,两个8位向量之间的乘法(即,向量的内乘)需要GF(2)域上的8次乘法和7次加法。但是如果两个向量定义为单字节数字,则部分乘法的运算将减少为1个逻辑与。类似地,向量加法也可以减少为1个异或操作。
在C语言中我们使用结构体来定义4x4矩阵,我们将矩阵每一行看作一个数,那么实现代码如下:

typedef unsigned char   uint8_t;
typedef struct M4
{
    uint8_t M[4];
}M4;

随机生成GF(2)上4X4的矩阵

使用时间作种子 srand(time(NULL)) ,让rand() 产生的随机数。因为我们将4X4矩阵的每一行看作一个数,而一个数只有4个bit,所以将rand()%16,取值范围为0-15.

#include<stdlib.h>
#include<time.h>
void GetRandMatrix4(M4 *MT) {
	
	srand((unsigned int)time(NULL));
	for (int i = 0; i < 4; i++)
	{
		(*MT).M[i]=rand()%16;
	}

}

判断GF(2)上有限域矩阵是否可逆

跟上篇文章的求解思路是一样,只不过现在,4x4矩阵中所有元素为0和1,我们不需要考虑系数,并且我们把一行看成一个数,需要分别与0x08, 0x04, 0x02, 0x01进行逻辑与操作提取相应的比特位。
实现代码如下:

int is_invert(M4 *MT) {
	int flag;
	M4 temp;
	copyM4(MT, &temp);
	int row_index;
	//消除为下三角矩阵
	for (int k = 0; k < 4; k++) {
		if ((temp.M[k] & idM4[k]) != 0) {
			for (int i = k + 1; i < 4; i++)
			{
				if ((temp.M[i] & idM4[k]) !=0) {
					temp.M[i] = temp.M[i] ^ temp.M[k];
				}
			}
		}
		else {
			flag = 1;
			for (int i = k + 1; i < 4; i++) {
				if ((temp.M[i] & idM4[k]) != 0) {
					swap4(i, k,&temp);
					flag = 0;
					break;
				}
			}
			if (flag) { 
				printf("\n矩阵不可逆\n");
				return 0; }
			for (int i = k + 1; i < 4; i++)
			{
				if ((temp.M[i] & idM4[k]) != 0) {
					temp.M[i] = temp.M[i] ^ temp.M[k];
				}
			}

		}
	}
	//判断对角线是否为0
	for (int i = 0; i < 4; i++) {
		if ((temp.M[i] & idM4[i]) == 0)
		{
			printf("\n矩阵不可逆\n");
			return 0;
		}
	}
	return 1;
}

求GF(2)上有限域矩阵的可逆矩阵

在矩阵可逆的前提下,我们可以计算GF(2)有限域上的可逆矩阵,需要把矩阵扩展为 [ M ∣ E ] [M|E] [ME],然后经过变化变为 [ E ∣ M − 1 ] [E|M^{-1}] [EM1] M − 1 M^{-1} M1即为可逆矩阵,为了减少代码复杂度,这里我们不单独构造一个扩展矩阵 [ M ∣ E ] [M|E] [ME],我们定义一个单位矩阵E,在每次M进行变化时,E跟着M进行变化,当M变为E时,E就变成了 M − 1 M^{-1} M1.
求解步骤如下
1)将矩阵化简为下三角矩阵
2)将矩阵化为单位矩阵E
求解详细思路参考上篇文章,代码实现如下:

void getInvertMatrix(M4 *MT) {
	M4 M_invert;
	for (int i = 0; i < 4; i++)
	{
		M_invert.M[i] = idM4[i];//初始化 E矩阵
	}
	for (int k = 0; k < 4; k++) {
		if (((*MT).M[k] & idM4[k]) != 0) {
			for (int i = k + 1; i < 4; i++)
			{
				if (((*MT).M[i] & idM4[k]) != 0) {
					(*MT).M[i] = (*MT).M[i] ^ (*MT).M[k];
					M_invert.M[i] = M_invert.M[i] ^ M_invert.M[k];
				}
			}
		}
		else {

			for (int i = k + 1; i < 4; i++) {
				if (((*MT).M[i] & idM4[k]) != 0) {
					swap4(i, k, MT);
					swap4(i, k, &M_invert);
					break;
				}
			}
			for (int i = k + 1; i < 4; i++)
			{
				if (((*MT).M[i] & idM4[k]) != 0) {
					(*MT).M[i] = (*MT).M[i] ^ (*MT).M[k];
					M_invert.M[i] = M_invert.M[i] ^ M_invert.M[k];
				}

			}
		}
	}
	//将右边的M矩阵,消除为单位矩阵E
	for (int  k = 1; k < 4; k++)
	{
		for (int i = 0; i < k; i++)
		{
			for (int j = 0; j < 4; j++)
			{
				if (((*MT).M[i]&idM4[k]) != 0){
				(*MT).M[i] = (*MT).M[i] ^ (*MT).M[k];
				M_invert.M[i] = M_invert.M[i] ^ M_invert.M[k];
				}
			}
		}
	}
	printf("\n可逆矩阵为\n");
	printfM4(&M_invert);
}

最终实验结果如下,将每个数化为4位二进制数,即可得到4x4的可逆矩阵
密码学基础——GF(2)有限域上的矩阵求逆文章来源地址https://www.toymoban.com/news/detail-481606.html

到了这里,关于密码学基础——GF(2)有限域上的矩阵求逆的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 密码学相关基础知识

    明文:没有经过加密,任何人都能看得懂的文字 密文:经过加密后的文字 密钥:明文与密文转换的参数 是现代密码学和古典密码学的重要区别 现代密码原则:密码系统的安全性不依赖于算法的保密而依赖于密钥的安全 古典密码原则:密码系统的安全性依赖于算法的保密和

    2023年04月27日
    浏览(37)
  • 密码学基础(一)——哈希算法

    一、常用密码学算法分类 哈希算法:哈希算法不可逆,包括:MD4、MD5、hash1、ripeMD160、SHA256、SHA3、Keccak256、国家标准SM3(国家密码管理局) 加密/解密算法:加密解密算法可逆,但是必须要有秘钥,对称加密,非对称加密,数字签名算法DSA 编码/解码算法:编码解码算法可逆

    2023年04月16日
    浏览(39)
  • 38_安全密码学基础

    在了解安全密码学之前,我们需要补充一些额外知识。 是基于拉丁字母的一套电脑编码系统,就好像这些字符,对应的就是十进制的65 97,简单来说就是计算机没有办法识别字符,他只理解01二进制,所以用一个字符表,规定了什么字符用什么01表示。 PBE(Password Based Encrypt

    2024年01月21日
    浏览(47)
  • 【密码学基础】RSA加密算法

    RSA是一种非对称加密算法,即加密和解密时用到的密钥不同。 加密密钥是公钥,可以公开;解密密钥是私钥,必须保密保存。 基于一个简单的数论事实:两个大质数相乘很容易,但想要对其乘积进行因式分解却极其困难,因此可以将乘积公开作为加密密钥,即公钥;而两个

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

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

    2024年02月07日
    浏览(41)
  • openssl基础使用(密码学 linux)

    openssl是Linux内置的一款开源工具,实现了常见的密码算法与应用。通过openssl操作,完成各种密码算法的应用。 创建一个文件,用于被加密,文件内容为12345,文件名为test.txt 一、对称加密 1、使用rc4加解密 加密 这是第一个是设置密码,第二个是重复输入密码。两次必须一样。

    2024年02月10日
    浏览(81)
  • 【密码学基础】半/全同态加密算法基础学习笔记

    定义:只支持乘法或加法中的一种的同态加密。同态加密指的是允许直接对密文进行计算,密文计算结果解密后与明文直接计算结果相同。 Paillier加解密过程 Paillier的同态性 明文加法 = 密文乘法 明文乘法 = 密文指数幂 Paillier的安全性 基于大整数分解困难问题 相比Paillier,

    2024年02月13日
    浏览(47)
  • 密码学基础(三)——数字签名与证书

    数字签名:又叫公钥数字签名,或者电子印章。 数字信息社会用于取代传统社会手写签名的一种公钥加密领域的技术实现。 数字签名其实就是非对称加密的私钥加密,公钥解密的过程。 数字证书用来证明公钥拥有者的身份,验证数据来源,验证数据是否被修改。 数字证书中

    2024年02月16日
    浏览(44)
  • 区块链基础之密码学及安全技术

    1.2 密码学及安全技术 1.2.1 密码学知识 1.2.1.1 Hash函数 Hash(哈希) 哈希函数是一类数学函数,可以在有限合理的时间内,将任意长度的消息压缩为 固定长度的输出值,并且是不可逆的。其输出值称为哈希值,也称为散列值。 哈希算法的应用: 消息认证:确保收到的消息和发送

    2024年02月11日
    浏览(41)
  • 【现代密码学基础】详解完美安全与不可区分安全

    目录 一. 介绍 二. 不可区分性试验 三. 不可区分性与完美安全 四. 例题 五. 小结 敌手完美不可区分,英文写做perfect adversarial indistinguishability,其中adversarial经常被省略不写,在密码学的论文中经常被简称为IND安全。 完美不可区分与香农的完美安全是类似的。该定义来源于一

    2024年01月21日
    浏览(53)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包