python可以做网站,织梦怎么做单页网站,linux 部署wordpress,韩国购物网站有哪些第1关#xff1a;哈希函数
题目
任务描述
本关任务#xff1a;利用哈希算法统计每个字符串出现的个数。
相关知识
为了完成本关任务#xff0c;你需要掌握#xff1a;1.密码学哈希函数的概念及特性#xff0c;2.安全哈希算法。
密码学哈希函数的概念及特性
我们需要…第1关哈希函数
题目
任务描述
本关任务利用哈希算法统计每个字符串出现的个数。
相关知识
为了完成本关任务你需要掌握1.密码学哈希函数的概念及特性2.安全哈希算法。
密码学哈希函数的概念及特性
我们需要理解的第一个密码学的基础知识是密码学哈希函数哈希函数是一个数学函数具有以下三个特性 ● 其输入可为任意大小的字符串。 ● 它产生固定大小的输出。为使本章讨论更具体我们假设输出值大小为256位但是我们的讨论适用于任意规模的输出只要其足够大。 ● 它能进行有效计算简单来说就是对于特定的输入字符串在合理时间内我们可以算出哈希函数的输出。更准确地说对应n位的字符串其哈希值计算的复杂度为On。 这些特性定义了一般哈希函数以这个函数为基础我们可以创建数据结构例如哈希表。我们将只专注于加密的哈希函数要使哈希函数达到密码安全我们要求其具有以下三个附加特性
碰撞阻力collision−resistance隐秘性hiding谜题友好puzzle−friendliness
下面具体阐述这三个特性
特性1碰撞阻力 加密的哈希函数的第一个特性是它要具有碰撞阻力。这里的碰撞指对于两个不同的输入产生相同的输出。如果对于哈希函数H(⋅)没有人能够找到碰撞我们则称该函数具有碰撞阻力。即如果无法找到两个值x和yx\\y而H(x)H(y)则称哈希函数H具有碰撞阻力特性2隐秘性 我们希望哈希函数拥有的第二个特性是其隐秘性。隐秘性保证如果我们仅仅知道哈希函数的输出yH(x)我们没有可行的办法算出输入值x。问题是上述的表示形式不一定是正确的。考虑以下简单的例子我们做一个抛硬币的实验如果抛硬币结果为正面我们会宣布字符串哈希为“正面”如果结果为反面我们会宣布字符串哈希为“反面”。 然后我们问我们的对手在他没有见到抛硬币而只见到哈希函数的输出的前提下说出哈希函数的输入字符串。为了回答问题对手会简单计算“正面”字符串的哈希值及“反面”字符串的哈希值然后对手便可以知道他得到的是哪一个。这样只需要几步对手就能反解出输入值。 对手能够猜出字符串这是因为x只有两个可能他可以很轻易地将两个可能对应的哈希值计算出来。为了能够实现隐秘性我们需要x的取值来自一个非常广泛的集合也就是说仅仅通过尝试几个特定的x就能找到输出值的方式将不会发生了。 现在的问题是在类似抛硬币的“正面”、“反面”实验中如果我们想要的反解的输入值并非来自分散的集合我们是否还能得到隐秘性幸运的是对于这个问题答案是肯定的我们甚至能够通过与另一个较为分散的输入进行结合而将一个并不分散的输入进行隐秘。现在我们可以更精确地表示隐秘的含义了双竖线‖为连接符号代表把一系列事件、事情等联系起来。即哈希函数H具有隐秘性如果当其输入r选自一个高阶最小熵highmin−entroy的概率分布在给定Hr‖x条件下来确定x是不可行的。特性3谜题友好 哈希函数需要的第三个安全特性为谜题友好特性。这一特性较为复杂我们首先解释该特性的技术要求然后通过举例来阐释该特性的意义。 直觉上谜题友好可以这样解释如果有一个人想找到y值所对应的输入假定在输入集合中有一部分是非常随机的那么他将非常难以求得y值对应的输入。即 如果对于任意n位输出值y假定k选自高阶最小熵分布如果无法找到一个可行的方法在比2n小很多时间内找到x保证H(k‖x)y成立那么我们称哈希函数H为谜题友好。
安全哈希算法
安全哈希算法SecureHashAlgorithm256简称SHA−256。哈希函数有很多但SHA−256是一个主要被比特币世界采用并且效果还很不错的哈希函数。 回想一下我们要求哈希函数可以用于任意长度输入。幸运的是只要我们能建立一个用于固定长度输入的哈希函数然后通过一般方法就可以将接受固定长度的哈希函数转化为可接受任意长度输入的哈希函数我们称这个转换过程为MDMerkle−Damgard变换SHA−256是采用这种变换方法的常用哈希函数之一。在通用术语中这种基础型可用于固定长度具备碰撞阻力的哈希函数被称为是压缩函数compressionfunction。经过验证如果基本压缩函数具有碰撞阻力的特性那么经过转换而生成的哈希函数也具有碰撞阻力。 MD变换很简单。比如压缩函数代入长度为m的输入值并产生长度短一些为n的输出值。哈希函数的输入可为任意大小被分为长度为m−n的区块。MD变换运作过程如下将每个区块与之前区块的输出一起代入压缩函数注意输入长度则变为(m−n)nm也刚好就是压缩函数的输入长度。对于第一个区块而言之前没有的区块我们需要选取一个初始向量。每次调用哈希函数这个数字都会被再一次使用而在实践中你可以直接在标准文档中找到它。最后一个区块的输出也就是你返回的结果。 SHA−256函数利用了这样的一个压缩函数这个压缩函数把一个768位的输入压缩成一个256位的输出每一个区块的大小是512位。
编程要求
根据提示在右侧编辑器补充代码输出每个字符串的次数具体格式看样例输出按照字符串的字典序从小到大输出。
测试说明
平台会对你编写的代码进行测试
测试输入 5 a ab abc a ab预期输出 a 2 ab 2 abc 1提示 可以使用mapstring,int
代码
用map统计一下每个字符串出现的次数即可。
#includebits/stdc.h
using namespace std;
//在下面Begin和End之间补全代码
/*********** Begin ***********/
int main()
{int n;cinn;string x;mapstring, int mp;for(int i0; in; i){cinx;auto it mp.find(x);if (it ! mp.end()) { // 键存在mp[x] mp[x] 1;} else {mp[x] 1;}}for (auto i : mp) {cout i.first i.second endl;}return 0;
}
/*********** End ***********/第2关数字签名
题目
任务描述
本关任务对给定的身份以及消息进行数字签名。
相关知识
为了完成本关任务你需要掌握1.数字签名的概念和性质2.公钥即身份。
数字签名的概念和性质
数字签名是密码学中的第二个重要部分。数字签名被认为是对纸上手写签名的数字模拟。我们对数字签名有两个特性要求使其与我们对手写签名的预期一致。
第一只有你可以制作你自己的签名但任何看到它的人都可以验证其有效性第二我们希望签名只与某一特定文件发生联系因此该签名不能用于表明你同意或支持另一份不同的文件。
对于手写签名来说第二条就如同确保别人不能将你的签名从一份文件上剪下来贴到另一份文件的末尾那样。 那我们如何通过密码学来构建这些性质呢首先让我们把之前的直观讨论说得更具体一些以便今后可以更好地论证数字签名方案并讨论其安全特性。 数字签名方案
(1)数字签名方案由以下三个算法构成 ● (sk,pk):generateKeys(keysize)generateKeys方法把keysize作为输入来产生一对公钥和私钥。私钥sk被安全保存并用来签名一段消息公钥pk是人人都可以找到的拿到它就可以用来验证你的签名。 ● sig:sign(sk,message) 签名过程是把一段消息和私钥作为一个输入对于消息输出是签名。 ●isValid:verify(pk,message,sig) 验证过程是通过把一段消息和签名消息与公钥作为输入如果返回的结果是真证明签名属实如果返回的结果为假证明签名消息为假。 (2)我们要求以下两个性质有效 ● 有效签名可以通过验证即 verify(pk,message,sign(sk,message))true ● 签名不可伪造。
公钥即身份
让我们来看一下与数字签名并行的一个有用技巧基本想法是从数字签名模式中拿出一个公共验证密钥并将其与一个人或一个系统参与者的身份对等。如果你见到一条消息的签名被公钥pk正确验证那么你可以认为pk就是在表达这条消息。你真的可以将公钥认为是参与者或者系统的一方他可以通过签署声明而发布声明。从这个角度来说公钥就是身份让某人能为pk身份发声他必须知道相应的密钥sk。 将公钥视为身份的一个结果是你可以随时制定新的身份——你可以简单通过数字签名方案中的generateKeys程序生成新的密钥对sk和pk。pk是你可以使用的新的公共身份sk是相应的密钥只有你自己知道并可以让你代表身份为pk发声。在实践中你可能会使用pk的哈希作为你的身份这是因为公钥很大。如果是这样的话为了验证消息来自你的身份人们会需要验证
1你的身份确实是pk的哈希2信息能经过公钥pk验证。
此外在默认情况下你的公钥pk基本上看起来是随机的也并没有人能够通过检查pk发现你的现实身份当然一旦你开始使用这个身份发表声明这些声明可能泄露信息而让别人将你的真实身份与pk联系起来。我们很快会更详细地讨论这个问题。你可以生成一个看起来随机的新身份看起来像人群中的一张脸但这些都只有你能够控制。
编程要求
根据提示在右侧编辑器补充代码根据公钥即身份我们可以模拟一次消息签名假如你的身份是e,有哈希函数H(x)axb,那么我们可以把pkH(e)作为公钥skH(e)−1modq作为私钥我们用私钥对消息m进行加密即en(m)sk∗m那么我们解密就可以这样计算de(en(m))en(m)∗pk。这里q保证是素数。 输入 e a b q m输出 pk sk en(m)输入 3 4 5 11 6输出
17212提示 费马定理求逆元可以查询一下。
代码
ksm求逆元
b 与 p 互质情况下若 a/b ≡ a*x (mod p)则 x 为 b 的乘法逆元
可转化为 b * x ≡ 1 (mod p)
费马定理若 p 为质数得bp-1 ≡ 1 (mod p)
又有b * x ≡ 1 (mod p)
得到b * bp-2 ≡ 1 (mod p)所以 x bp-2
// 题目规定 p 是质数我们使用费马定理需要 a p 是互质并且 p 是质数
// 只有 a 是 p 得倍数时不互质if (a % p 0) System.out.println(impossible);
else System.out.println(quick_power(a, p - 2, p));// 快速幂
private static long quick_power(long a, long k, long p) {long ans 1;while (k 0) {if ((k 1) 1) ans ans * a % p;k 1;a a * a % p;}return ans;
}#includebits/stdc.h
using namespace std;
int e,a,b,q,m;// 快速幂求逆元
long ksm(long a, long k, long p) {long ans 1;while (k 0) {if ((k 1) 1) ans ans * a % p;k 1;a a * a % p;}return ans;
}// 哈希函数
int H(int x) {return a * x b;
}// 公钥
int pk() {return H(e);
}// 私钥
int sk() {return ksm(H(e), q-2, q);
}// 加密
int en() {return sk() * m;
}int main()
{cineabqm;cout pk() endl;cout sk() endl;cout en() endl;return 0;
}
