算法题目

[JS: Interview Algorithm]https://thatjsdude.com/interview/js1.html)

1 质数verify

问题： 验证质数
基本方法：

function isPrime(n){
  var divisor = 2;

  while (n > divisor){
    if(n % divisor == 0){
     return false; 
    }
    else
      divisor++;
  }
  return true;
}

> isPrime(137);
  = true
> isPrime(237);
  = false

优化方法： 起初的时候，每次增长1，但是3以后，可以每次增长2。也就是说，可以只验证3之后的奇数，因为如果一个数可以被偶数整除，那一定能被2整除，所以3以后就不用偶数验证了。

2 质因子

问题： 求给定数的所有质因子
基本方法： 如下

function primeFactors(n){
  var factors = [], 
      divisor = 2;
  
  while(n>2){
    if(n % divisor == 0){
       factors.push(divisor); 
       n= n/ divisor;
    }
    else{
      divisor++;
    }     
  }
  return factors;
}

这其实更多的是一个数学问题，code上其实很容易

3 斐波那契

问题： 求斐波那契数列的第n个元素
基本方法： 如下

function Fib(n) {
  if (n <= 2) {
  	return 1
  } else {
	return Fib(n-1) + Fib(n-2)
  }
}

递归的时间复杂度是2^n

4 数组去重

问题： 任意数组进行去重操作
基本方法： 如下

function removeDup(arr) {
	var exists = {}
	var rtn = []
	for (var i = 0; i < arr.length;  i++) {
		if(!exists[arr[i]]) {
			rtn.push(arr[i])
			exists[arr[i]] = true
		}
	}
	return rtn
}

用hash table来降低时间复杂度

SSR深入研究

为什么写这些东西？

渐渐意识到，记录日志的价值。以前认为，记录一些日常生活和工作的感想，是一件有些矫情的事情。但是慢慢发现，记录下来自己的感想，可以帮助自己进行总结和思考，理清思路，保持心态。而在现如今这个非常复杂的社会环境中，保持心态，这件看似很简单同时很重要的事情，确很难办到，非常容易受到环境的影响，至少我经常被影响到。认识一些朋友，能够保持很好的心态，不轻易被环境影响，用自己的坐标系评价自己。在这里做记录的目的，也就是慢慢建立自己的评价体系。

为什么选择软件和互联网？

我大学修的传统工科专业，也从事过传统机电行业的研发工作。之后研究生，在日本严谨而良好的科研氛围下，严肃认真的搞过两年真正的科学研究，还发过论文。
我决心进入软件和互联网行业，就是基于之前学习积累的一些体会，总结起来，大致如下几点：
首先，传统行业发展成熟，不在社会的热点上，职业发展的机会和待遇都明显不如软件和互联网。这个是现实的必然选择。
其次，做研究的经历，让我感受到学术圈的限制，在独立之前你的一举一动都要受到导师的限制，从性格上并不适合于我，学术自由也许90%的研究人员都无缘实现。相比而言，软件是自由的，互联网技术更是自由的，很多自学成才的技术人的故事都说明了这一点。当然对于这种自由能带来的深入程度和自己事业发展的空间想象，需要我更多的去体会。

如何获得机会？

1. 自己要克服心理限制，积极主动的尝试和沟通；
2. 为人诚恳豁达，就会获得别人获得不到的机会。
3. 机会留给有准备的人，对现状不满，但是更好的又得不到之前，我需要的是踏实的学习。想到和得到之间是做到。

如何取得进展和突破？

1. 专注积累沉淀。对一个领域的专精要比对十个领域的了解好得多。
2. 有作品有产出。尽可能做一些输出和实践，有记录的那种。
3. 产品角度思考问题。你的专业价值能解决别人的什么问题，解决的问题越多，你的价值就越高。

JWT-DeepStudy

关于JWT的研究笔记

Study1

5 Easy Steps to Understanding JSON Web Tokens (JWT)

JWT是一个标准，有严格定义的定义，一般来说由header、payload和signature三个部分组成。简单来说，JWT只是一个如下格式的字符串：
header.payload.signature

JWT的构建和校验过程可以分为下面5个步骤：
Step1: 创建header
header包含如何计算JWT签名的信息，header是一个以下格式的JSON对象:

{
	typ: 'JWT',
	alg: 'HS256'
}

alg键对应的值表示使用了哪种hash算法来创建JWT签名。

Step2 创建payload
payload是JWT用于保存数据的部分，比如用户ID,

{
	userid: 'asdad-asdfasdfa-asdffasdf'
}

Step3: 创建signature
用下面的伪代码来说明这个流程：

data = base64urlEncode(header) + '.' + base64urlEncode(payload)
signature = Hash( data, secret) 

这个算法先使用base64url编码step1和step2中创建的header和payload。然后使用'.'将已经编码的字符串拼接。使用jwt header中指定的hash算法，加上密钥对拼接字符串进行hash得到signature

Step4 将JWT的三个部分组合起来
最终拼接完整的JWT字符串：heade.payload.signature

Step5: 校验JWT
当用户使用附带JWT的请求调用API时，应用可以执行STEP3中相同的签名算法（服务知道算法和secret），然后，应用可以验证自身创建的签名是否与JWT中的附带签名一致，如何一致，则表示JWT是有效的，表明API请求来源可信。

JWT如何保护数据？
通过上面的过程，可以发现JWT中的数据只是被编码和签名，并没有被加密。
编码的目的是为了转换数据的结构，对数据签名来保证接受者可以校验数据的来源。当然，编码和签名不能保护数据。JWT的目的是为了验证数据的来源可靠性。

Study2

My Experience with JSON Web Tokens
关于JWT还有一些地方缺乏consensus，主要有三点：
• Where should JWT be stored
• How to prevent common attacks like CSRF and XSS
• How to revoke tokens in case they are compromised

Where to store JWTs - cookies vs web storage

对于在哪里保存JWT的问题存在很多的争议，HTTP cookie 还是 H5 Web storage呢？

使用web storage的问题是，会存在XSS攻击的问题，因为web storage是可以通过js获取的，那么就存在被攻击的可能。

相比而言，cookie要更安全一点，通过给cookie设置HttpOnly flag，可以控制让js脚本不能读取cookie，这样就减少了XSS攻击。另外，cookie还可以设置secure flag，这样JWT就只能通过HTTPS传递，这样也能保护Man-in-the-middle的攻击。（这也可以认为是cookie和localstorage在web安全层面的一些不同！）

但是，除了XSS之外，CSRF是对cookie的巨大威胁。因为cookie是浏览器默认发送的，这样攻击者通过设计CSRF攻击，诱使用户发出已经authenticated过的请求。

好消息是，减少CSRF攻击的一个很简单的方案是：要求所有的请求都要包含token，通常这被称为，CSRF token。在用户登录之后，将token发送给客户端，然后要求后面的所有请求都必须包含这个token的header（header不是浏览器自动发送的，需要程序控制，不是CSRF能控制的了）

结论：虽然web storage和http cookie都会有安全性上的一些问题，但是相比较而言，CSRF要比XSS攻击更容易避免一些。所以还是选择在cookie中保存JWT。

Dealing with compromised JWTs

这里compromise没有很好的翻译，大意就是要取消当前的token。在下面两种情况下，需要compromise JWT:
1. 一个已经授权过的设备lost或者stolen了，在这样的情况下，我们需要能够取消用户的所有token，比如让他们从设备上登出。
2. JWT被盗，这样的情况会复杂一些。但是我们可以从用户请求的异常中发现，比如从不同的IP发出请求或者发出请求的客户端的user-agent属性冲突。这些时候我们可以要求取消当前JWT，然后重新认证。

对于这种compromised JWT的情况，可以通过下面的方式进行解决：

用户登陆成功之后，发出一个short-lived JWT，并且在db里保持相应的验证信息，比如revoke标签，ip或者user-agent字段等信息。之后的每个请求，会检查JWT的expiration日期（这个信息应该包含在token本身中）。如果过期了，则需要通过db里的记录进行验证，如果通过，则返回一个新的JWT。否则拒绝请求。

Study3

Encoding vs. Encryption vs. Hashing vs. Obfuscation

之前的学习过程中强调了，JWT实际上是编码和hash的过程，而并没有加密。那么编码(Encode)、哈希(Hash)、加密(Encryption)和混淆(Obfuscation)这几个概念的区别是什么呢？

Encoding
Encoding的目的是对数据进行变形（transform），这样数据才能合理并安全的被其他系统使用。比如通过邮件发出的二进制数据，或者网页上的特殊字符。encoding的目的不是将信息进行保密，而是为了保证数据能够被合适的使用。

Encoding使用一种大家知道的规则对数据进行变形，所以encoding可以很容易的逆向。这个过程中也不需要密钥，只需要知道encode的算法，就可以逆向的decode.

常用的encode：ASCII, UNICODE, URL ENCODING, BASE64等

Encryption

encryption的目的是，通过将数据进行变形，从而实现保密的目的。比如发送给一封只有收信人才能理解的信，或者通过网络发送密码等。所以encryption的目的不是在数据的可用性(usability上)，目标是保证数据不会被目标接收人之外的人消费。

所以encrytion对数据进行变形(transform)，变形的算法只有固定的人可逆操作。在这个过程中，会使用key，key和原始的平文通过算法生成加密后的密文。

常用的有： AES, BLOWFISH, RSA

Hashing

Hashing的目的是保证数据的完整性，如果数据发生了变化，这个变化可以被检查出来。技术上来说，hashing接收任意的输入，生成固定长度的字符串，并且遵守下面的规则：
1. 同样的input总是生成同样的output
2. 不同的输入不能得到相同的output
3. 从output到input这个过程是不可逆的
4. 对input的一点修改都会output产生巨大的变化

Hash通常可以在用户验证领域用来确认信息没有被修改过。

常用的有：SHA-3等。

Obfuscation
obfuscation的目的是让一些信息更难理解，从而避免攻击和复制。一个常用的场合就是对源代码的混淆，避免被盗用。

常用的有： JAVASCRIPT OBFUSCATOR等。

Study4

关于token的expiration

基于passportjs做认证相关的开发时，创建jwt token是依赖passport-jwt这个package的encode API. 通过设置exp属性，就可以给这个token加一个生效的期限，如下 ：

function tokenForUser(user) {
  const timestamp = new Date().getTime() / 1000;
  return jwt.encode({
    sub: user.id,
    iat: timestamp,
    exp: timestamp + 30
  },
  config.secret);
}

另外，此处exp的单位应该是s而不是ms。

关于验证时候expire，用户是不用自己判断的。passport-jwt自动做了判断。passport-jwt中有一verify函数如下：

var jwt = require('jsonwebtoken');

module.exports  = function(token, secretOrKey, options, callback) {
    return jwt.verify(token, secretOrKey, options, callback);
};

可以看出真正在起作用的是jsonwebtoken，也其实才是core module.
下面是一段直接利用jsonwebtoken API的一些尝试：

var jwt = require('jsonwebtoken');
var secret = 'asdfadadsfadfasddf'; 

var token = jwt.sign({ // 生成token
	foo: 'bar' ,
	exp: Math.floor(Date.now() / 1000) + 5, // 5秒的expiration
}, secret);

console.log('generated token: ', token)

verifyToken(token); // verify 生成的token

setTimeout(function() {
	verifyToken(token)
}, 6000); //延迟6秒再次verify

function verifyToken(token) {
	jwt.verify(token, secret, function(err, decode) {
		if (err) {
			console.log('err', err.toString());
		} else {
			console.log('decode', decode);
		}
	})
}

输出的结果如下：

generated token:  eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJmb28iOiJiYXIiLCJleHAiOjE1Mjc4MjQ4NjgsImlhdCI6MTUyNzgyNDg2M30.D3l671_TpE4QTjuPqQSb5c_-z0u1Ts5ANlKbUAVLS5Q
decode { foo: 'bar', exp: 1527824868, iat: 1527824863 }
err TokenExpiredError: jwt expired

Study5

最近读到一些tutorial，发现JWT token的一个新知识，token分为两种access token和refresh token。access token就是正常用来获取资源的token，而这个refresh token在应用中的作用是。当access token到期expire之后，需要更新一个新的access token，如果需要再次登录的话，那用户使用起来就不方便了。

而更方便的架构是，当用户signup或者signin之后，生成两个token：access token和refresh token。除此之外，再开发一个API接口，需要更新access token的时候，用户发送refresh token，经过验证，获取新的access token。

主程序文件如下，逻辑写在注释里：

const express = require('express')
const bodyParser = require('body-parser')
const jwt = require('jsonwebtoken')
const router = express.Router()
const config = require('./config')
const tokenList = {}
const app = express()

router.get('/', () => {
	res.send('ok');
});

router.post('/login', (req, res) => {
	const postData = req.body;
	const user = {
		email: postData.email,
		name: postData.name
	}
	// 生成两个token: access token 和 refresh token
	const token = jwt.sign(user, config.secret, { expiresIn: config.tokenLife });
	const refreshToken = jwt.sign(user, config.refreshTokenSecret, { expiresIn: config.refreshTokenLife });
	// expiresIn是jsonwebtoken这个包提供的一个参数，也能实现expire的功能
	const response = {
		'status': 'logged in',
		'token': token,
		'refreshToken': refreshToken,
	}
	tokenList[refreshToken] = response
	res.status(200).json(response)
})

// token路由，用于生成新的access token
router.post('/token', (req, res)  => {
	const postData = req.body
	if ((postData.refreshToken) && (postData.refreshToken in tokenList)) {
		const user = {
			email: postData.email,
			name: postData.name
		}
		// 重新生成一个access token
		const token = jwt.sign(user, config.secret, { expiresIn: config.tokenLife })
		const response = {
			token: token,
		}
		// 更新内存中的access token
		tokenList[postData.refreshToken].token = token;
		res.status(200).json(response);
	} else {
		res.statsu(404).send('Invalid request')
	}
});

// check token的middleware
router.use(require('./tokenChecker'))

router.get('/secure', (req, res) => {
	res.send('I am secured...')
})

app.use(bodyParser.json())
app.use('/api', router)
app.listen(config.port || process.env.port || 3000);

config.js的配置文件如下：

{
    "secret": "some-secret-shit-goes-here",
    "refreshTokenSecret": "some-secret-refresh-token-shit",
    "port": 3000,
    "tokenLife": 900,
    "refreshTokenLife": 86400
}

tokenChecker中间件：

const jwt = require('jsonwebtoken');
const config = require('./config');

module.exports = (req, res, next) => {
	const token = req.body.token || req.query.token || req.headers['x-access-token']
	
	if (token) {
		jwt.verify(token, config.secret, function(err, decoded) {
			if (err) {
				return res.status(401).json({ error:true, message: 'Unauthorized access' });
			}
			req.decoded = decoded;
			next();
		})
	} else {
		return res.status(403).send({
			error: true,
			message: 'No token provided'
		})
	}
}