数学事实

反复线性和非线性交替计算

代码js

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
function md5(string) {
function RotateLeft(lValue, iShiftBits) {
return ((lValue << iShiftBits) | (lValue >>> (32 - iShiftBits))) & 0xFFFFFFFF;
}

// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER
function unsignAdd(lX, lY) {
return ((lX & 0xFFFFFFFF) + (lY & 0xFFFFFFFF) ) & 0xFFFFFFFF;
}

// (a,b,c,d) = (d, ((a+f(b,c,d) + data + Ki)<<< s)+b, b, c)
function f(a, b, c, d, x, s, ac, Fn) {
return unsignAdd(RotateLeft(unsignAdd(a, unsignAdd(unsignAdd(Fn(b, c, d), x), ac)), s), b);
}

function ConvertToWordArray(string) {
let lWordCount;
let lMessageLength = string.length;
// https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Number/MAX_SAFE_INTEGER
let lNumberOfWords_temp1 = lMessageLength + 8;
let lNumberOfWords_temp2 = (lNumberOfWords_temp1 - (lNumberOfWords_temp1 % 64)) / 64;
let lNumberOfWords = (lNumberOfWords_temp2 + 1) * 16;
let lWordArray = Array(lNumberOfWords - 1);
let lBytePosition = 0;
let lByteCount = 0;
while (lByteCount < lMessageLength) {
lWordCount = (lByteCount - (lByteCount % 4)) / 4;
lBytePosition = (lByteCount % 4) * 8;
lWordArray[lWordCount] = (lWordArray[lWordCount] | (string.charCodeAt(lByteCount) << lBytePosition));
lByteCount++;
}
lWordCount = (lByteCount - (lByteCount % 4)) / 4;
lBytePosition = (lByteCount % 4) * 8;
lWordArray[lWordCount] = lWordArray[lWordCount] | (0x80 << lBytePosition);
lWordArray[lNumberOfWords - 2] = lMessageLength << 3;
lWordArray[lNumberOfWords - 1] = lMessageLength >>> 29;
return lWordArray;
};
function WordToHex(v) {
let WordToHexValue = "";
for (let i = 0; i < 4; i++) {
WordToHexValue += `0${((v >>> (i * 8)) & 0xFF).toString(16)}`.substr(-2);
}
return WordToHexValue;
};
function Utf8Encode(string) {
let utftext = "";
for (let n = 0; n < string.length; n++) {
let c = string.charCodeAt(n);
if (c < 128) {
utftext += String.fromCharCode(c);
} else if ((c > 127) && (c < 2048)) {
utftext += String.fromCharCode((c >> 6) | 192);
utftext += String.fromCharCode((c & 63) | 128);
} else {
utftext += String.fromCharCode((c >> 12) | 224);
utftext += String.fromCharCode(((c >> 6) & 63) | 128);
utftext += String.fromCharCode((c & 63) | 128);
}
}
return utftext;
};
let x = ConvertToWordArray(Utf8Encode(string));

let funcs = [
(x,y,z) => ((x & y) | ((~x) & z) ),
(x,y,z) => ((x & z) | (y & (~z))),
(x,y,z) => (x ^ y ^ z),
(x,y,z) => (y ^ (x | (~z)))
];
// K = abs(sin(i+1))*(2^32) int part
// https://softwareengineering.stackexchange.com/questions/89694/md5-implementation-notes
const K = [ 0xD76AA478 ,0xE8C7B756 ,0x242070DB ,0xC1BDCEEE ,0xF57C0FAF ,0x4787C62A ,0xA8304613 ,0xFD469501 ,0x698098D8 ,0x8B44F7AF ,0xFFFF5BB1 ,0x895CD7BE ,0x6B901122 ,0xFD987193 ,0xA679438E ,0x49B40821 ,0xF61E2562 ,0xC040B340 ,0x265E5A51 ,0xE9B6C7AA ,0xD62F105D ,0x02441453 ,0xD8A1E681 ,0xE7D3FBC8 ,0x21E1CDE6 ,0xC33707D6 ,0xF4D50D87 ,0x455A14ED ,0xA9E3E905 ,0xFCEFA3F8 ,0x676F02D9 ,0x8D2A4C8A ,0xFFFA3942 ,0x8771F681 ,0x6D9D6122 ,0xFDE5380C ,0xA4BEEA44 ,0x4BDECFA9 ,0xF6BB4B60 ,0xBEBFBC70 ,0x289B7EC6 ,0xEAA127FA ,0xD4EF3085 ,0x04881D05 ,0xD9D4D039 ,0xE6DB99E5 ,0x1FA27CF8 ,0xC4AC5665 ,0xF4292244 ,0x432AFF97 ,0xAB9423A7 ,0xFC93A039 ,0x655B59C3 ,0x8F0CCC92 ,0xFFEFF47D ,0x85845DD1 ,0x6FA87E4F ,0xFE2CE6E0 ,0xA3014314 ,0x4E0811A1 ,0xF7537E82 ,0xBD3AF235 ,0x2AD7D2BB ,0xEB86D391 ] ;

const S = [[7,12,17,22],[5,9,14,20],[4,11,16,23],[6,10,15,21]];

const offset = [[1,0],[5,1],[3,5],[7,0]];

// 01234567 89abcdef fedcba98 76543210
let abcd = [0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476];

// http://www.faqs.org/rfcs/rfc1321.html
for (let idx = 0; idx < x.length; idx += 16) {
const ABCD = [...abcd];
for(let i = 0;i < 4;i ++){
for(let j = 0;j < 4;j ++){
for(let k = 0;k < 4;k ++){
abcd = [abcd[3],f(...abcd, x[idx + ((offset[i][0]*(j*4+k) + offset[i][1] ) %16)], S[i][k], K[(i*4+j)*4+k], funcs[i]),abcd[1],abcd[2]];
}
}
}
abcd = ABCD.map((item,idx)=> unsignAdd(item,abcd[idx]));
}
return abcd.map(item=>WordToHex(item)).join('').toLowerCase();
}

console.log(md5(""))
console.log(md5("demo"))

两段看起来复杂的函数 其实 是字符串通过utf8/ascii之类转换成 数值

其中一些值和公式的设计大自能有个想法感受了,还不明白的是offset和s的设计为什么是这样的,搜了半天也没搜到

https://en.wikipedia.org/wiki/MD5

数论事实

两个大质数相乘,只需要最多两个数字长度的乘积的复杂度,而把两个质数乘积进行拆分可能要 其中较小数字的时间复杂度。也就是易于验证,难于破解。

假设两个长度为2048(二进制下)的质数相乘,最多只需要 2048 x 2048的时间,而枚举拆分需要2^2048的时间, 目前最快的?gnfs算法的复杂度也是

$O(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac 13}(\log\log N)^{\frac 23}})$

加解密

加密

$C=M^e \bmod n$

n=pq,其中p和q为大质数

M 要加密的信息 (需要 和n互质也就是至少p,q其中一个互质,1/pq 当质数足够大时碰撞概率极小,其实因为公钥信息里已经有n了,也不会碰撞)

e 和 (p-1)(q-1)互质,简单些 e直接取小于 (p-1)(q-1)的质数

公钥(e,n), 所有人都知道

解密

私钥匙$(e,p,q)$

$de = 1 \bmod ((p-1)(q-1))$,计算d,d是e关于(p-1)(q-1)的乘法模逆元 log 级别复杂度

$ C^d = (M^e)^d = M^{ed} = M^{1+k(p-1)(q-1)} (\bmod n)$

费马小定理:p质数,a和p互质,$a^{p-1} = 1 (\bmod p)$

如果 M 和p 互素, 有 $C^d = M\cdot (M^{p-1})^{k(q-1)} = M \cdot 1^{k(q-1)} = M \cdot 1 = M (mod p)$ 即是 $ C^d - M = 0 (mod p) $

否则 $ M = 0 \bmod p$, $ C^d = (M^e \bmod n)^d = (0^e)^d = 0 (\bmod p) $,也有 $C^d - M = 0(\bmod p)$

同理 有$C^d - M = 0 (\bmod q)$

因此 $C^d - M = 0 (\bmod (n=pq))$即$C^d = M (\bmod n)$

也就是 我们通过幂次直接拿到 M在$\bmod n$的意义下

安全

也就是公钥里只有(e,n), 计算不出p和q, 就意味着计算不出(p-1)(q-1),也就计算不出d,也就无法直接d的幂次。

另一个问题就是 模运算 是否有办法开e次根。

在就是历史信息,如果有人(机器)能拆解n,那么所有用到相应公私钥的信息都能被破解了。

所以据说 现在512位的似乎已经被认为不安全了。可以类似NFS, GNFS,SIQS, 和ECM 定向爆破。https://blog.csdn.net/tigerisland45/article/details/51348854

穷举自己可以按(10^10) 需要1台计算机一秒来估计,是不可能的。例如枚举需要 2**512//(10**10)//60//60//24//365 = 42515880041674902015392012297710065092210064119077858250011293263957902175524946019792853558367907875729426237273230754863501657825807236 台计算机 年

而好处是,如果始终拆解质数乘积是难的,那么只需要单纯的增加位数即可,这样在实现上的额外代价就是生成代价,对应的拆解代价是按照幂次增长。

而生成的代价,解密的代价较大,注定了它用在少量数据,而剩余的数据加密,还是要靠对称加密。

使用

产生3072 bits的私钥(不要分享)

openssl genrsa -out private.pem 3072

通过私钥产生公钥(可以给任何人)

openssl rsa -in private.pem -out public.pem -outform PEM -pubout

产生原始消息(模拟要给你发信息的人)

echo 'too many secrets' > file.txt

通过你提供的公钥加密(并把加密后的信息发给你)

openssl rsautl -encrypt -inkey public.pem -pubin -in file.txt -out file.ssl

你通过私钥解密

openssl rsautl -decrypt -inkey private.pem -in file.ssl -out decrypted.txt

查看消息

cat decrypted.txt

如何使用ssh-keygen 生成的公私钥

众所周知,一般上个git之类都会用openssh提供的 ssh-keygen生成公私钥。但是公钥不能像上面那样直接用

方法是用id_rsa.pub 转换,生成一个openssl能使用的PEM格式再用

ssh-keygen -f ~/.ssh/id_rsa.pub -e -m PKCS8 > id_rsa.pem.pub

剩余的操作和上面一样

contact

加密联系我

id_rsa.pub

1
ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABgQDgFNXLxLccaE5w6GBHwg+sqXXphmEDgxjTQj6UYgu1et0yIqY2NU6ouAp91SnQAsW6htF1g6X7SjVuW4cgN+3R4nCociNBwvzPIiUbInhn1J5oaI3wRktWLOlxqUO1ykvsCjoZty+wfMvy5zFnG6+bjkn3i0WfCNoEOiHuaOJd+dt0l0Kha6+QdIHj6zLPH65y/oW5WJWe4iZoOjmBKJ+Ps9oGVMJxOZDCTWCUJQV1DFZgo7WAkT2/Thfz390sNiuclDE6rpmLPAqCGjtOO4zhoUpwq35QmTNjlg5PutM6s+SQZMnX2ZKgkUV/QWNenC40yS/L0Sj57ZCHvbEenh8v4YC4YRcW2BrdSloaPmhne1tH5xpw/By7UKAG/S3liebb5B3tjLpvjI0EU8l6/I6JxAtYe19tKpDPC/J1Z1L1nQ//rjDiVayg0u4Ti1grngTcTogTU9ttvwGFgdBCBkI/4xQB8kkSXllMLf2AmocFjyU/TFa1fgw+PBv8Ydi+T48= yexiaorain@gmail.com

ref

https://en.wikipedia.org/wiki/RSA_numbers

About

目前看到angular2+ 官方的使用是 karma + jasmine

Can I use Karma with testing framework X?

Yes. There are plugins for most of the common testing frameworks (such as Jasmine, Mocha, QUnit). If there is no plugin for the testing framework you like, go ahead and write one. It is simple - you can start by looking into the source code of the existing ones.

karma创建一个web server。

浏览器通过手动方位 karma server 监听的地址(默认9876),或者自动让karma 知道运行哪个browsers,来让浏览器可以被捕获

可用的列表http://karma-runner.github.io/5.0/config/browsers.html

karma 能力

见下面 paper的pdf内容

在真实环境中测试

支持远程控制

执行速度快

可以跟第三方 IDE 进行交互

支持 ci 服务

高扩展性,支持插件开发

支持调试

对比

paper 3.1的表

阿里云

主要目标

paper 2.1

  1. 真实设备上运行测试

  2. 远程控制

  3. 高效, 无缝隙使用流程

  4. Integration with IDEs and text editors

  5. Integration with CI Servers

  6. 扩展性

  7. Debugging

包含 client/server,基于Http 通信

设计和分析

Chapter 4

  • 速度

  • 可靠性

  • 在真实浏览器上测试 并

  • seamless workflow

服务端

paper 4.1

监听文件

与 client 进行通讯

向开发者输出测试结果

提供 client 端所需的资源文件

Manager

跟client双向通讯,例如开始和结束测试,收集测试结果

Web Server

Web Server, 给客户端提供静态资源文件

Reporter

给开发者输出报告

File System Watcher

检测变化并通知client,类似 一些热更新之类的?

Client

可以 多client 对1个server

Manager

和server双向通信

Testing Framework

框架内自己没有,可以用很多三方的framework,例如上面的jasmine

Tests and Code under Test

这是开发者编写的内容了

…….我感觉阿里社区里面那个翻译也不错。。可以不用继续啃英文了

总结

测试的代码 全部在客户端运行,这个客户端是真实的客户端,它可以是chrome,firefox等等

karma主要的工作是支撑测试的提供,例如静态文件服务,文件变化监听等,而具体代码测试内容是在karma启动的客户端(浏览器)中,依靠用户编写的测试代码和第三方测试框架完成的。

refs

http://karma-runner.github.io/5.0/intro/how-it-works.html

https://raw.githubusercontent.com/karma-runner/karma/master/thesis.pdf

https://fed.taobao.org/blog/taofed/do71ct/karma-origin/

https://medium.com/@me_37286/yoni-goldberg-javascript-nodejs-testing-best-practices-2b98924c9347

ProjectEuler 74 题

https://projecteuler.net/problem=74

用rust写了一遍,觉得根据常识1e6数据量,应该1s内随便跑,结果5s+,

就换成C++写了一遍,发现是因为rust没开O2?开了以后还真就和C++差不多的时间

rust 版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
use std::collections::HashMap;
const N:usize = 1_000_000;

fn next_value(mut value:usize,fac:&[usize]) -> usize{
let mut sum = 0;
while value != 0 {
sum += fac[value%10];
value/=10;
}
return sum;
}

fn dfs(
fac:&[usize],
ans:&mut HashMap<usize,usize>,
dep:&mut HashMap<usize,usize>,
value:usize
) -> (usize,usize) { // dep, len
let nv = next_value(value,fac);
let next_dep = dep.get(&value).unwrap() + 1;
match dep.get(&nv) {
Some(rs) => {
// println!("{} => {}",value,next_dep - rs);
ans.insert(value,next_dep - rs);
return (*rs,next_dep - rs);
},
None => {
match ans.get(&nv) {
Some(res) => {
let newres= (*res) + 1;
// println!("{} => {}",value,newres);
ans.insert(value,newres);
return (next_dep,newres);
},
None => {
dep.insert(nv,next_dep);
let mut ret = dfs(fac,ans,dep,nv);
if next_dep <= ret.0 {
ret.1 += 1;
}
// println!("{} => {}",value,ret.1);
ans.insert(value,ret.1);
return ret;
}
}
}
}
}

fn main() {
let mut fac = [0;11];
let mut ans = HashMap::new();
fac[0] = 1;
for i in 1..11{
fac[i] = fac[i-1]*i;
}
for i in 1..N+1{
if ans.contains_key(&i) {
continue;
}
let mut dep = HashMap::new();
dep.insert(i,0);
dfs(&fac,&mut ans,&mut dep,i);
}
let mut cnt = 0;
for (k, v) in &ans {
if *v >= 60 && *k <= N {
cnt+=1;
// println!("{}: \"{}\"", k, v);
}
}
println!("{}",cnt);
}

C++版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ten5 100000+10
#define MOD 1000000007
#define rep(i,a,n) for (uint i=a;i<n;i++)
#define iif(c,t,f) ((c)?(t):(f))
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
const double pi = acos(-1.0);

const uint N = 1'000'000;

uint next_value(uint value,uint *fac) {
uint sum = 0;
while(value != 0){
sum += fac[value%10];
value/=10;
}
return sum;
}

pair<uint,uint> dfs(
uint *fac,
unordered_map<uint,uint> &ans,
unordered_map<uint,uint> dep,
uint value
) { // dep, len
uint nv = next_value(value,fac);
uint next_dep = dep[value] + 1;
if(dep.count(nv)){
auto rs = dep[nv];
// printf("%d => %d\n",value,next_dep - rs);
ans[value] = next_dep - rs;
return {rs,next_dep - rs};
}else {
if(ans.count(nv)) {
auto res = ans[nv];
auto newres= res + 1;
// printf("%d => %d\n",value,newres);
ans[value] = newres;
return {next_dep,newres};
}else{
dep[nv] = next_dep;
auto ret = dfs(fac,ans,dep,nv);
if(next_dep <= ret.first){
ret.second += 1;
}
// printf("%d => %d\n",value,ret.second);
ans[value] = ret.second;
return ret;
}
}
}

int main() {
uint fac[11];
unordered_map<uint,uint> ans;
fac[0] = 1;
rep(i,1,11){
fac[i] = fac[i-1]*i;
}
rep(i,1,N+1){
if(ans.count(i)){
continue;
}
unordered_map<uint,uint> dep;
dep[i] = 0;
dfs(fac,ans,dep,i);
}
auto cnt = 0;
for (auto [k,v]: ans) {
if( v >= 60 && k <= N ){
cnt+=1;
// println!("{}: \"{}\"", k, v);
}
}
printf("%d",cnt);
return 0;
}

rust不带-O2 大概5s+,带了和C++相近都是0.3s左右, 真的快

env

Intel Core i7-7700HQ @ 8x 3.8GHz

!clang++ -o "%<" "%" -std=gnu++17 -O2 -g -Wall -Wcomma

1
2
3
clang version 6.0.0-1ubuntu2 (tags/RELEASE_600/final)
Target: x86_64-pc-linux-gnu
Thread model: posix

!rustc "%" -O

rustc 1.43.1 (8d69840ab 2020-05-04)

感受

rust写好的代码转换成C++是真的轻松,C++转换成rust就会很累(除非各种 as,unwrap