We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
该篇文章介绍了用Reed-Solomon编码的思想来比较两个大文件的内容。原文请戳这里: https://hackmd.io/@Kurt-Pan/SJ6Y0DZLq# 主要是想说明一个确定性比较算法的下界。我们暂时不讨论这么技术的问题。我们重点关注下Reed-Solomon编码这个思想来解决这个问题所带来的一些思考。因为这个问题,跟我之前做Shamir secret sharing的密码学算法很像,都是根据多项式来编码一些数据,然后通过拉格朗日插值来进行恢复原始数据
首先定义两个文件内容,文件A的内容记为向量a = (a1,a2,a3,..., a_n), 文件B的内容记为向量b = (b1,b2,b3,... b_n)。这些向量的元素你可以看成就是文件里面的字符了。Alice拥有文件A, Bob拥有文件B。按照朴素传统的确定性算法思想,要比较两个大文件内容就是Alice 把整个文件A发送给Bob, Bob执行算法验证 a_i 是否等于 b_i 逐个字符比较。但是,我们前面说了,这个文件是大文件了。Alice的文件发送给Bob这个动作,数据传输量太大了,通信复杂度很高。由于文章说了,如果有没有更好的确定性算法比这个朴素算法还好的,那么就没有,因为这个朴素算法就是下界。有没有可能可以突破下界,争取更好的复杂度,答案是放宽条件,用非确定性算法,允许有概率出错。这样就可以突破下界了。
原文它是设计了一种reed-solomon指纹识别协议,思想借用了RS编码。算法是把待编码的字符向量映射到一个有限域Fp下的多项式。向量字符值就是多项式的系数向量,以前我提到过的,系数向量就可以确定唯一的一个多项式。在这里,向量的大小n也就是多项式的degree了。
原始的RS编码: 把待编码的message定义为 x = (x1,x2,x3, ... , x_k ) x ∈ F
多项式: p(a) = x1*a^0 + x2*a^1 + ... + x_k * a^(k -1) a ∈ F
定义一个指纹hash函数:
F_p为素域, r ∈ F_p。 定义 Hash函数 H_r(x) = H_r(x1, x2, x3, ... , x_n) = x1*r^1 + x2*r^2 + x3* r3 + ... + x_n*r^n
具体协议:
你会看到这里的r在每一轮选择多项式上的一个点。而我们的RS编码,一段消息x的码字 C(x) 实际要选择n个点:
在Shamir Secret Sharing中,n 比 k大, 是 n >= 2*k + 1 , 对于degree 为 k - 1的多项式 ,那么知道其中任意k个点,那么都可以通过这k个点,把多项式插出来。所以RS编码中的网络上大多数找到的方案,都需要在编码的后面补足一个冗余的多项式,就是为了防止数据错乱,带有恢复校验的功能,不然RS编码就不叫纠错码(ECC, error-correct code)了。如果要了解详情,请看这里 https://crypto.stackexchange.com/questions/1760/rs-erasure-coding-and-shamirs-secret-sharing, 本质上threshold主要都是为了纠错(error-correction)。
The text was updated successfully, but these errors were encountered:
固定 step 取字符比较
Sorry, something went wrong.
固定 step 会有安全性问题,容易被伪造
哈哈,主要是想写reed solomon编码。这个编码在无线通信和卫星信号传输上都有用。这个文件比较只是采用了部分思想解决的问题。
固定 step 取字符比较 哈哈,主要是想写reed solomon编码。这个编码在无线通信和卫星信号传输上都有用。这个文件比较只是采用了部分思想解决的问题。
这种编码属于很底层了吧,是我宁愿看下压缩/安全方面的编码 偏应用层的
不底层,就是一种纠错码。压缩我以前只知道一个huffman,其实这个对普通文本压缩率蛮不错的,通用的压缩一般是根据重复串建模,需要点概率论的意思。你以前是搞特定数据的压缩还是通用数据的压缩啊?
No branches or pull requests
前言
该篇文章介绍了用Reed-Solomon编码的思想来比较两个大文件的内容。原文请戳这里: https://hackmd.io/@Kurt-Pan/SJ6Y0DZLq#
主要是想说明一个确定性比较算法的下界。我们暂时不讨论这么技术的问题。我们重点关注下Reed-Solomon编码这个思想来解决这个问题所带来的一些思考。因为这个问题,跟我之前做Shamir secret sharing的密码学算法很像,都是根据多项式来编码一些数据,然后通过拉格朗日插值来进行恢复原始数据
正文
首先定义两个文件内容,文件A的内容记为向量a = (a1,a2,a3,..., a_n), 文件B的内容记为向量b = (b1,b2,b3,... b_n)。这些向量的元素你可以看成就是文件里面的字符了。Alice拥有文件A, Bob拥有文件B。按照朴素传统的确定性算法思想,要比较两个大文件内容就是Alice 把整个文件A发送给Bob, Bob执行算法验证 a_i 是否等于 b_i 逐个字符比较。但是,我们前面说了,这个文件是大文件了。Alice的文件发送给Bob这个动作,数据传输量太大了,通信复杂度很高。由于文章说了,如果有没有更好的确定性算法比这个朴素算法还好的,那么就没有,因为这个朴素算法就是下界。有没有可能可以突破下界,争取更好的复杂度,答案是放宽条件,用非确定性算法,允许有概率出错。这样就可以突破下界了。
原文它是设计了一种reed-solomon指纹识别协议,思想借用了RS编码。算法是把待编码的字符向量映射到一个有限域Fp下的多项式。向量字符值就是多项式的系数向量,以前我提到过的,系数向量就可以确定唯一的一个多项式。在这里,向量的大小n也就是多项式的degree了。
原始的RS编码: 把待编码的message定义为 x = (x1,x2,x3, ... , x_k ) x ∈ F
多项式: p(a) = x1*a^0 + x2*a^1 + ... + x_k * a^(k -1) a ∈ F
定义一个指纹hash函数:
F_p为素域, r ∈ F_p。 定义 Hash函数 H_r(x) = H_r(x1, x2, x3, ... , x_n) = x1*r^1 + x2*r^2 + x3* r3 + ... + x_n*r^n
具体协议:
你会看到这里的r在每一轮选择多项式上的一个点。而我们的RS编码,一段消息x的码字 C(x) 实际要选择n个点:
在Shamir Secret Sharing中,n 比 k大, 是 n >= 2*k + 1 , 对于degree 为 k - 1的多项式 ,那么知道其中任意k个点,那么都可以通过这k个点,把多项式插出来。所以RS编码中的网络上大多数找到的方案,都需要在编码的后面补足一个冗余的多项式,就是为了防止数据错乱,带有恢复校验的功能,不然RS编码就不叫纠错码(ECC, error-correct code)了。如果要了解详情,请看这里 https://crypto.stackexchange.com/questions/1760/rs-erasure-coding-and-shamirs-secret-sharing, 本质上threshold主要都是为了纠错(error-correction)。
The text was updated successfully, but these errors were encountered: