和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}

继续阅读

RAIDZ

一、什么是 RAIDZ

RAIDZ 是 SUN Microsystem 在其 ZFS 文件系统中采用的软件 RAID 的解决方案。

二、 RAIDZ 出现背景

RAIDZ 出现的背景是因为硬件 RAID 没有表现出其声称应达到快速、可靠的效果,存在问题之一就是一个称为 RAID-5 “ write hole ”的缺陷: RAID 的写实分为两步的,首先更新数据,其次更新校验(将新数据和旧校验异或以使得所有磁盘异或为零)。如果这个写的过程中发生断电、系统崩溃等故障时,这是磁盘上存储的数据和校验就不匹配了,如果没有一个好的日志或快照机制来进行恢复的话,错误的数据将永远保存在磁盘上而无法纠正,而这一切对用户都是不知道的。为解决这一问题,有用户采用昂贵的 NVRAM 进行断电保护。

三、RAIDZ

RAIDZ 并不是真正意义上的 RAID,而是一种更高层的解决方案,所以它不需要像 RAID 一样的额外设备,使用动态的条带宽度,并利用了 ZFS 中类似于 RAID 的一种完整性冗余机制——写时备份(COW,copy-on-write)解决了 RAID-5 的 “ write hole ”问题:首先数据写到一个新的位置,接着再改写原来指向旧数据的指针,避免了小写必须读后写的操作而在全条带上进行写,利用小块镜像来代替奇偶校验,这是因为能够知道文件系统存储结构并能够在需要的时候分配额外的空间,RAID-Z2 是 RAIDZ 的升级, RAIDZ 采用的是类似 RAID-5 的单个奇偶校验位,RAIDZ-Z2 是采用类似于 RAID-6 的两个奇偶校验,这样前者允许一个磁盘损坏,而后者可以允许两个磁盘损坏而不丢失数据。

四、其他

另外一个需要谈到的是 RAIDZ 是伴随着 ZFS 文件系统产生的, RAIDZ 可以利用 ZFS 文件数据的校验和与其他机制进行错误检测和更正,它对所有的数据进行校验并在有正确副本的时候对错误数据进行恢复。下图给出了硬件 RAID-5 和 RAIDZ 的速度比较,需要提出的时,硬件实现的速度快但 RAIDZ 优势在于不需要购买其他设备。

 

 

 

 

百度百科也通过 RAIDZ