WoW登录过程简介

登录过程采用SRP协议,具体版本细节不清楚,反正不是最新版。

相关记号:
    H ---- 单向Hash函数,WoW中用的是Sha1,Sha1生成的结果定长20字节
    N ---- 大素数,32字节
    g ---- N%(一个N的质因子),1字节
    C ---- 明文用户名
    P ---- 明文密码
    CP ---- C + ":" + P,+表示字符串连接
    s ---- 随机数
    x ---- 临时变量,x = H(s, H(CP))
    v ---- v = g ^ x
    a ---- 随机数,保存在客户端,不公开
    b ---- 随机数,保存在服务器,不公开
    A ---- A = g ^ a
    B ---- B = 3 * v + g ^ b
    u ---- u = H(A, B)
    S ---- 客户端:S = (B - 3 * g ^ x) ^ (a + u * x),服务器:S = (A * v ^ u) ^ b,都为32字节
    Key ---- 40字节,偶数字节为H(S的偶数字节),奇数字节为H(S的奇数字节),Key将用于以后的通讯加密
    M1 ---- M1 = H( H(N) xor H(g), H(C), s, A, B, Key )
    M2 ---- M2 = H( A, M1, Key)
    ^ ---- 幂运算
    xor ---- 异或运算
    % ---- 模运算
    所有运算结果都%N
   

登录过程(只包含正常的流程,错误检测忽略):
    0、服务器预先保存着N和g。
    1、客户端向服务器发送C。
    2、服务器根据C查找P。生成s、v、b、B,将B、g、N、s发送给客户端。
    3、客户端生成a、x、v、A、u、S、M1、M2,将A、M1发送给服务器。
    4、服务器生成S、Key、M1、M2,将M2发送给客户端。
    5、如果两边的M1和M2都一致,则登录成功。

Pick's Theorem

今天做到某题(POJ 2954),题意是求一个顶点坐标均为整数的三角型内整数点的个数,不含三角型边上的整数点。

Pick's Theorem,大意是:任何平面上顶点坐标均为整数的简单多边形,满足以下公式:

A = I + B / 2 - 1

A是多边形的面积,I是多边形内的整数点的个数,B是多边形边上整数点的个数。

Pick's Theorem可以推广到多维的情况,见:Ehrhart polynomials

理论和题目配合得相当完美……汗啊……