和NTL(Number Theory Library) 比较有限域上矩阵求秩

下载了NTL(Number Theory Library),简单对正方矩阵(square matrix)求秩和nclib 进行了测试,测试参数如下:

  • 有限域大小为:GF(28)、GF(216)和GF(232)
  • 正方矩阵维度从2 到255(横坐标)

测试方法:随机生成指定大小的矩阵,计算其秩大小,仅计算一次。

测试结果如下(分别是GF(28)、GF(216)和GF(232) 域上的结果):

 

320816

在域大小为GF(28)和GF(216)时差别还不是很大,但为GF(232) 时,计算速度差距就有些大了,主要还是矩阵的表示方法不同,nclib 用uint_8/uint_16/uint_32 类型表示三个域中元素,而NTL 中域中元素全部二进制表示,计算秩更多的使用了单个元素求逆和而不是像nclib 建立域上计算表。比如GF(232) 上进行求秩,方阵很小的时候速度也很慢,是把有限域上计算表(乘法表、对数表)时间给算进去了。nclib 可以对此进行改进。

相关文件

由IPhone 密码锁想到的零知识证明

事情源于国庆、中秋双节回家,看到Lina 总是背着我输入IPhone 密码想到的(上次因为输入密码次数过多导致重新刷机,所以她不让我碰她的IPhone),我猜想这:如果我能够瞄她输入密码的数字和顺序,那么我就可以知道并记住密码,并在“偷”到IPhone 后以同样的密码进入。为了避免密码输入被人偷窥到而导致密码泄露,自然而然会有些想法:一、有没有什么方式让每次输入的密码都不同;二、更进一步,有没有哪种方式让她当着我的面输入密码,我也不知道密码是什么呢?

继续阅读

使用Python Crypto.Cipher 测试AES 加密速度

Crypto 提供AES 加/解密。有几点需要注意:

  1. 密钥key 长度必须为16(AES-128),24(AES-192),或者32 (AES-256)Bytes 长度
  2. 每次使用encrypt( ) 方法加密的内容必须为16 Bytes 长度
  3. Crypto AES加密模式有ECB/CBC/CFB 等模式,ECB 不需要使用iv 参数,CBC 等链式模式需要iv 参数
  4. ECB 是最简单的分块加密方式,CBC 当前加密结果和之前所有加密块都有关系,抗频率分析
  5. iv 是用于链式加密的参数,加密时长度必须等于AES.block_size,解密时长度为block_size+2 Bytes

继续阅读

POTSHARDS: Secure Long-Term Storage Without Encryption

原文地址

summary:文章介绍了一种在不可信的存储提供商(Storage Service Provider)上建立长期文档的可信存储,采用的方法不是加密而是秘密分享(secret sharing)技术。首先文章谈到文档系统应该满足几个安全特性:

  1. 授权用户必须能够访问数据
  2. 即使缺少密钥,计算适当时间后也可以访问数据
  3. 保证数据的完整性,用户所读到的数据是之前写入的,而不是被篡改的。

Secret Sharing/Spliting 秘密分享

Secret Sharing 最早是 1979 年由 Adi Shamir 和 George Blakley 提出来的。很早看十万个为什么数学板块的时候,红楼梦里的王熙凤将百宝箱上了四把锁,将钥匙分为四份,每个人拿着两份,只有任意 2 个人一起来开箱子才能够把箱子打开(如下图),这应该也是一种(2-4)秘密分享的技术吧!但是这与现代的秘密分享还有不同。

 \begin{tabular}{||c||c||c||c||} \hhline{|t:=:t:=:t:=:t:=:t|}$Key_1$ & $Key_2$ & $Key_3$ &$Key_4$ \\ \hhline{|:=:b:=::=:b:=:|}\multicolumn{2}{||c||}{$User_1$}&\multicolumn{2}{c||}{}\\ \hhline{|:=:t:=:b:=:t:=:|}&\multicolumn{2}{c||}{$User_2$}&\\ \hhline{|:=:b:=:t:=:b:=:|}\multicolumn{2}{||c||}{}&\multicolumn{2}{c||}{$User_3$}\\ \hhline{|:=:t:=:b:=:t:=:|}{$User_4$}&\multicolumn{2}{c||}{}&{$User_4$}\\ \hhline{|b:=:b:==:b:=:b|} \end{tabular}

继续阅读