计算机安全：算法优化
公钥算法的优化
加密算法的两个重要指标是加密强度和速度。在实现上，可以用各种技术来提高算法速度。加密算法分为密钥生成和加解密，主要优化加解密部分。Amdahl定律：优化一段代码的效果，取决于其执行时间占全部执行时间的比例。
优化工作的方向
充分利用CPU特性，如流水线和指令并行
针对加密算法本身做一些优化
编译器也会做一些优化：编译器的优化很保守(保证正确性)，且一些优化对于程序员来说简单，对编译器来说很难
软件优化一般方法代码移动预计算指令替换共享子表达式减少多余过程调用限制变量利用指令并行：调整代码顺序，使相近的两条指令的数据不相关将条件分支指令按照概率和计算量排列次序如先计算一个定值，先计算一个字符串的长度避免使用耗时的指令：如左右移指令不能与任何其他指令配对形成流水，阻断了流水线在循环中避免使用条件跳转指令：条件跳转指令会产生不可预见的指令流，容易分支预测失败展开加密循环和函数：减少了条件指令和计算指令，将变量转化为常量，减少流水线的阻断和指令预取的作废限制变量的数量：寄存器有限变量长度与CPU内部寄存器长度相同:否则，需要用别的指令来辅助存取，增加了指令周期数
...
计算机安全：安全协议
身份证明协议
两个参与者：证明者，验证者。
采用方式：挑战-响应协议-证明者向验证者通过展示与身份相关的秘密知识，证明自己的身份。
关键：不泄露秘密，且能够抵抗攻击。
双向认证(基于共享密钥)基于整数模p的阶为q的乘法循环群基于公钥的认证
挑战：一方传送给对方一个随机数
响应：对方对这个数进行特定处理再返回
双向认证协议(1)
假设A也是可接受多个会话的通用计算机
考虑当攻击者伪装B的身份
受到反射攻击：
关键：1.攻击者伪装B，建立一个同A的会话；2.攻击者拦截一个A向B的会话；3.攻击者利用A的自动加密，分别套出两个随机数的加密值。
双向认证协议(2)
受到反射攻击：
改进方式：在每个加密消息里加入发送者、接收者在协议中的角色(这样攻击者就无法利用消息2)。
双向认证协议(3)基于HMAC，对HMAC的 攻击难于对对称密钥算法的攻击。
双向认证协议(4)Andrew安全RPC协议。
攻击：
重放攻击：重放4给A；4中没有注明这个会话密钥和此次通信的关联。
类型缺陷攻击：攻击者在第四步重放2给A：虽然攻击者不一定知道RA+1，但猜测nonce ...
计算机安全：快速比特操纵算法
快速比特操纵算法含义
使用机器字操作(算术、逻辑运算)实现机器字中的比特的计算和变换，是一种时间复杂度与机器字长无关的算法。
计算1的个数
朴素方法移位加法方法乘法方法乘法和加法的综合使用更快的方法1234unsigned int v; //c的值即1的个数 unsigned int c; for (c = 0; v; c++) v &= v - 1; 分块和
对于一个二进制数x（总位数为w），将其划分为多段相同长度u的区间，将每个区间内的1的个数转化为二进制，首尾相接得到y：y称为x的u分块和。
例如：101010的1分块和是1,0,1,0,1,0,101010的2分块和是01,01,01，101010的6分块和是000011。
因为u位能表示的最大个数，大于等于u的长度，故该方式能正确表达出分块和而不发生溢出。
递推表达式x[2u]=yAND(0u1u)w/2u+(x[u]>>u)AND(0u1u)w/2u说明
简单来说，便是将奇数个u区间和偶数个u区间相加。
例如上面01010101的例子：先将 ...
计算机安全：安全计算
协议双方互不信任，都有可能欺骗
Semi-honest 半诚实，遵守协议流程，在过程中获得尽可能的信息
承诺方案
即在一次信息交换中，A和B需要“同时”获得对方的一个信息。假设A先给出信息a，B后给出信息b。则B需要先给出b的证明c，A再给出信息a，B再给出信息b。这样，A能够核验信息证明c，来确保B没有在接收信息a后更改信息b【绑定】；同时，A也无法从信息证明c中获取b，来改变信息a【隐藏】。
基于Hash函数的实现
A 计算承诺 c = H (随机数,a)，将 c 发送给 B
隐藏性：存在 H ( R’, a’ ) = H ( R, a )，B找不到真实的R，a
绑定性： A 找不到 R’, a’，满足：H ( R’, a’ ) = H ( R, a )
不存在对有无限计算能力的敌手同时具有隐藏性和绑定性的承诺方案。
百万富翁问题
A有一个0-9的数a，B有一个0-9的数b，A和B不想让对方知道自己的数字，但想知道a和b的大小。
基于DH实现茫然传输方案混淆电路方案
A和B生成 α,gα,β,gβ
A进行操作后发给B：若α=i ...
计算机安全：俄国农民指数算法
俄国农民指数算法
正向快速幂(R-L算法)逆向快速幂(L-R算法)比较123456789101112long long FastPow(long long g,long long e,const long long m) //求g的e次方模m的值{ long long ans=1; while(e) { if(e&1) ans=(ans*g)%m; g=(g*g)%m; e>>=1; } return ans;}123456789101112long long FastPow(long long g,long long e,const long long m) //求g的e次方模m的值{ long long ans=1; while(e) //e采用反向存储 { ans=(ans*ans)%m; if(e&1) a ...
计算机安全：蒙哥马利约减
蒙哥马利约减
目前使用最广泛的模指数运算方法
问题
求y mod N，N为质数。y称为x模N关于R的Montgomery约减,即y=xR’ mod N
附加条件：不使用除法（除法速度慢）
尽量避免使用取模运算用移位、减法运算替代取模运算
设计
1.取R为2的n次方(如果 N表示为n个b进制数，则 R取b的幂次方)，这样/ R即右移，*R即左移，mod R即与（R-1）按位与，大大提高了速度。
2.N<R,R和N互质，即存在R’和N’，使得RR’ + NN’＝1(保证对任意的x＜R，有k＜R，使得kN=x＜R。这保证表达式(见下文)的后半部分有解，且大小不超过R/R=1)。同时，加上y/R＜N，故表达式的前半部分大小不超过N。综上可得，表达式整体大小不超过2N(故取模可以用减法做)。
推导设T=Qm+r，欲求T mod m将T分为n的两部分，高n位为T’，低n位为T’’则：TRmodm=T′modm+0.T″modm前半部分只需要移位和最多一次减法。对于后半部分，需要找到0.km，使其与 ...
欢迎来到第九边缘
(function(d, w, c) {
w.ChatraID = 'D5JbrYK4vHavdTNTf';
var s = d.createElement('script');
w[c] = w[c] || function() {
(w[c].q = w[c].q || []).push(arguments);
};
s.async = true;
s.src = 'https://call.chatra.io/chatra.js';
if (d.head) d.head.appendChild(s);
})(document, window, 'Chatra');
一、什么是第九边缘文化体系“第九边缘是什么？相信并不是所有人都能够意识到。包括我们的代理者，也不能轻易做出一个明确的定义。或许，第九边缘并不符合他们的文化倾向。但在我们的世界里，第九边缘意味着“理性的文化”。它作为一个哲学符号，又或者是文明的动态象征，第九边缘的创造 ...