Algorithms
本周算法题：
Roman to Integer
注：本题解法来自以下两个文章：
http://www.cnblogs.com/grandyang/p/4120857.html
https://www.jiuzhang.com/solution/roman-to-integer/#tag-highlight-lang-cpp
学习到罗马数字的使用方式，之前对此没有细致的了解。
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
| class Solution {
public:
int romanToInt(string s) {
int ans = 0;
ans = toInt(s[0]);
for (int i=1; i<s.length(); i++) {
ans += toInt(s[i]);
if (toInt(s[i-1]) < toInt(s[i])) {
ans -= toInt(s[i-1]) * 2;
}
}
return ans;
}
int toInt(char s) {
switch(s) {
case 'I':return 1;
case 'V':return 5;
case 'X':return 10;
case 'L':return 50;
case 'C':return 100;
case 'D':return 500;
case 'M':return 1000;
}
return 0;
}
};
|
Longest Common Prefix
思路：从第一个字符开始找，如果全部相同，继续查找下一个字符，直到遇到不同的字符。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.size() == 0) {
return "";
}
if (strs.size() == 1) {
return strs[0];
}
for (int i=0; i<strs[0].size(); i++){
for (int j=1; j<strs.size(); j++){
if (strs[j][i] != strs[0][i]){
return strs[j].substr(0, i);
}
}
}
return strs[0];
}
};
|
Review
本周阅读英文文章Password and Credential Management in 2018
如果密码能够任意长，在使用PBKDF2算法时会增加所需的时间和计算资源，可以通过重复提交长密码来进行Dos攻击。
在用户登录时，从数据库加载加密的哈希值，使用Vault对其解密，并将其与生成的哈希值进行比较以进行身份验证时，建议进行constant time comparison。
constant time comparison相关：
https://codahale.com/a-lesson-in-timing-attacks/
https://crypto.stackexchange.com/questions/39429/why-not-use-or-in-constant-time-comparison
Key derivation function
Argon2
bcrypt
scrypt
PBKDF2
Technique
在阅读《HTTP/2基础教程》中学习到使用OpenSSL来调试HTTP/2。
OpenSSL命令：
1
| echo | openssl s_client -connect akah2san.h2book.com:443 -servername akah2san.h2book.com -alpn spdy/2,h2,h2-14 | grep ALPN
|
显示：
1
2
3
4
5
6
7
8
9
| $ echo | openssl s_client -connect akah2san.h2book.com:443 -servername akah2san.h2book.com -alpn spdy/2,h2,h2-14 | grep ALPN
depth=2 O = Digital Signature Trust Co., CN = DST Root CA X3
verify return:1
depth=1 C = US, O = Let's Encrypt, CN = Let's Encrypt Authority X3
verify return:1
depth=0 CN = akah2san.h2book.com
verify return:1
ALPN protocol: h2
DONE
|
其中| grep ALPN会过滤输出。如果省略这个命令，可以看到openssl s_client这个命令的所有输出，其中包含调试TLS配置的相关信息。完整的输出里面包含证书链、证书、协商使用的加密协议，还有其他各种细节。可以将书中例子akah2san.h2book.com替换为百度和必应体验一下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| $ echo | openssl s_client -connect www.baidu.com:443 -servername www.baidu.com -alpn spdy/2,h2,h2-14 | grep ALPN
depth=2 C = BE, O = GlobalSign nv-sa, OU = Root CA, CN = GlobalSign Root CA
verify return:1
depth=1 C = BE, O = GlobalSign nv-sa, CN = GlobalSign Organization Validation CA - SHA256 - G2
verify return:1
depth=0 C = CN, ST = beijing, L = beijing, OU = service operation department, O = "Beijing Baidu Netcom Science Technology Co., Ltd", CN = baidu.com
verify return:1
No ALPN negotiated
DONE
$ echo | openssl s_client -connect www.bing.com:443 -servername www.bing.com -alpn spdy/2,h2,h2-14 | grep ALPN
depth=2 C = IE, O = Baltimore, OU = CyberTrust, CN = Baltimore CyberTrust Root
verify return:1
depth=1 C = US, ST = Washington, L = Redmond, O = Microsoft Corporation, OU = Microsoft IT, CN = Microsoft IT TLS CA 5
verify return:1
depth=0 CN = www.bing.com
verify return:1
ALPN protocol: h2
DONE
|
Share
本周分享在nosec看到的文章： 安装Python库时执行任意代码