T-OTP for Google Authenticator

Google Authenticator采用的算法是T-OTP（Time-Based One-Time Password），需要知道以下三点信息：
   ＊ Key: 共享密钥
   ＊ Current Time: 当前时间输入
   ＊ HMAC-SHA1函数

共享密钥
共享密码用于在手机端上建立账户。密码内容可以是通过手机拍照二维码或者手工输入，并会被进行base32加密。

手工密码的输入格式如下：

    xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx

包含该令牌的二维码的内容是一个URL：

    otpauth://totp/Google%3Ayourname@gmail.com?secret=xxxx&issuer=Google

时间输入(当前时间)

输入的时间值来自于手机，一旦注册获得密钥后，就无需与服务器再进行通信，所以要确保手机上的时间准确，因为往后的步骤服务器可能会验证多个收到的OTP token，但时间值服务器只会取当前时间： 服务器会比对所有提交的token以确认是否有正确输入。

Hash函数

验证所用的方法是HMAC-SHA1，以一个密钥和一个消息为输入，生成一个20字节消息摘要作为输出。其算法可以简单表示为：

    hmac = SHA1(secret + SHA1(secret + input))

T-OTP与H-OTP的区别是T-OTP以当前时间作为输入，而H-OTP以自增counter(based on a seed)作为输入，该计数器使用时需要两边同步。

算法

首先，要进行密钥的base32加密。虽然谷歌上的密钥格式是带空格的，不过base32拒绝空格输入，并只允许大写。所以要作如下处理：

    original_secret = xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 
    secret = BASE32_DECODE(TO_UPPERCASE(REMOVE_SPACES(original_secret)))

第二步要获取当前时间值，这里使用的是UNIX time函数，或者可以用纪元秒。

    input = CURRENT_UNIX_TIME()

在Google Authenticator中，input值拥有一个有效期。因为如果直接根据时间进行计算，结果将时刻发生改变，那么将很难进行复用。Google Authenticator默认使用30秒作为有效期(时间片)，最后input的取值为从Unix epoch（1970年1月1日 00:00:00）来经历的30秒的个数。

    input = CURRENT_UNIX_TIME() / 30

最后一步是进行HMAC-SHA1运算

    1.original_secret = xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 

    2.secret = BASE32_DECODE(TO_UPPERCASE(REMOVE_SPACES(original_secret))) 

    3.input = CURRENT_UNIX_TIME() / 30 

    4.hmac = SHA1(secret + SHA1(secret + input))

HMAC运算后的结果会是20字节即40位16进制数，我们需要的是常规6位数字密码. 首先要对20字节的SHA1进行瘦身。我们把SHA1的最后4个比特数（每个数的取值是0~15）用来做索引号，然后使用从索引号开始的4个字节计算OTP。因此，索引号的操作范围是15+4=19，加上是以零开始，所以能完整表示20字节的信息。4字节的获取方法是：

    1.然后将它转化为标准的32bit无符号整数(4 bytes = 32 bit)：

    2.large_integer = INT(four_bytes)

最后再进行7位数(1百万)取整，就可得到6位数字了：

    1.large_integer = INT(four_bytes) 

    2.small_integer = large_integer % 1,000,000

这也是我们最后要的目标结果，整个过程总结如下：

    1.original_secret = xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxxx 

    2.secret = BASE32_DECODE(TO_UPPERCASE(REMOVE_SPACES(original_secret))) 

    3.input = CURRENT_UNIX_TIME() / 30 

    4.hmac = SHA1(secret + SHA1(secret + input)) 

    5.four_bytes = hmac[LAST_BYTE(hmac):LAST_BYTE(hmac) + 4] 

    6.large_integer = INT(four_bytes) 

    7.small_integer = large_integer % 1,000,000

一个完整可执行的GO语言程序，可以这里进行查看:
http://garbagecollected.org/2014/09/14/how-google-authenticator-works/