Basics - Web Encrypt

Shannon Entropy

Codes from: http://rosettacode.org/wiki/Entropy

(function(shannon) {
  // Create a dictionary of character frequencies and iterate over it.
  function process(s, evaluator) {
    var h = Object.create(null), k;
    s.split('').forEach(function(c) {
      h[c] && h[c]++ || (h[c] = 1); });
    if (evaluator) for (k in h) evaluator(k, h[k]);
    return h;
  };
  // Measure the entropy of a string in bits per symbol.
  shannon.entropy = function(s) {
    var sum = 0,len = s.length;
    process(s, function(k, f) {
      var p = f/len;
      sum -= p * Math.log(p) / Math.log(2);
    });
    return sum;
  };
})(window.shannon = window.shannon || {});

// Log the Shannon entropy of a string.
function logEntropy(s) {
  console.log('Entropy of "' + s + '" in bits per symbol:', shannon.entropy(s));
}

logEntropy('1223334444');
logEntropy('0');
logEntropy('01');
logEntropy('0123');
logEntropy('01234567');
logEntropy('0123456789abcdef');

Output:

Entropy of "1223334444" in bits per symbol: 1.8464393446710154
Entropy of "0" in bits per symbol: 0
Entropy of "01" in bits per symbol: 1
Entropy of "0123" in bits per symbol: 2
Entropy of "01234567" in bits per symbol: 3
Entropy of "0123456789abcdef" in bits per symbol: 4

Birthday attack

生日问题是指，如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级（30人）中，存在两人生日相同的可能性更高。对于60或者更多的人，这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论，从这个数学事实与一般直觉相抵触的意义上，它才称得上是一个悖论。大多数人会认为，23人中有2人生日相同的概率应该远远小于50%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。

Euler Theorem

$\gcd(a, n) = 1$

$a^{\phi(n)} ≡ 1 (\bmod n)$

当 $p$ 为质数时（费马小定理）：

$\phi(p) = p - 1$

所以

$a^{p-1} ≡ 1 (\bmod p)$

Euler Totient Function

任意给定正整数 $n$ ，小于等于 $n$ 的正整数之中，有多少个与 $n$ 构成互质关系，计算这个值的方法就叫做欧拉函数，以 $\phi(n)$ 表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 $\phi(8) = 4$ 。

一、 $n=1$
如果 $n=1$ ，则 $\phi(1) = 1$ 。因为1与任何数（包括自身）都构成互质关系。

二、 $n$ 是质数
如果n是质数，则 $\phi(n)=n-1$ 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

三、 $n$ 是质数的某一个次方，即 $n = p^k$ ( $p$ 为质数， $k$ 为大于等于1的整数)
$\phi(p^{k}) = p^{k} - p^{(k-1)}$

比如 $\phi(8) = \phi(2^{3}) =2^{3} - 2^{2} = 8 - 4 = 4$

$\phi(p^{k}) = p^{k} - p^{(k-1)} = p^{k} * (1 - \frac{1}{p})$

四、 $n$ 可以分解成两个互质的整数之积，即 $n = p_{1} \times{} p_{2}$
$\phi(n) = \phi(p_{1}\times{}p_{2}) = \phi(p_{1})\times{}\phi(p_{2})$

比如 $\phi(56)=\phi(8\times{}7)=\phi(8)\times{}\phi(7)=4\times{}6=24$

五、任意一个大于1的正整数，都可以写成一系列质数的积
$n = p_{1}^{k_{1}} \times{} p_{2}^{k_{2}} \times{} \cdot\cdot\cdot \times{} p_{n}^{k_{n}}$

$\phi(n) = \phi(p_{1}^{k_{1}}) \times{} \phi(p_{2}^{k_{2}}) \times{} \cdot\cdot\cdot \times{} \phi(p_{n}^{k_{n}})$

$\phi(n) = p_{1}^{k_{1}} \times{} p_{2}^{k_{2}} \times{} \cdot\cdot\cdot \times{} p_{n}^{k_{n}} \times{} (1 - \frac{1}{p_{1}}) \times{} (1 - \frac{1}{p_{2}}) \times{} \cdot\cdot\cdot \times{} (1 - \frac{1}{p_{n}})$

$\phi(n) = n \times{} (1 - \frac{1}{p_{1}}) \times{} (1 - \frac{1}{p_{2}}) \times{} \cdot\cdot\cdot \times{} (1 - \frac{1}{p_{n}})$

$\phi(n)=n\prod_{p|n}\left(1-\frac{1}{p}\right)$

比如 $\phi(1323) = \phi(3^{2} \times 7^{2}) = 1323 \times (1 - \frac{1}{3}) \times (1 - \frac{1}{7}) = 756$

public static BigInteger euler(BigInteger x) {
    BigInteger res = x;
    for (BigInteger i = BigInteger.valueOf(2); i.compareTo(x.divide(i)) <= 0; i = i.add(BigInteger.ONE)) {
        if (x.mod(i).equals(BigInteger.ZERO)) {
            res = res.divide(i).multiply(i.subtract(BigInteger.ONE));
            while (x.mod(i).equals(BigInteger.ZERO)) {
                x = x.divide(i);
            }
        }
    }
    if (x.compareTo(BigInteger.ONE) > 0) {
        res = res.divide(x).multiply(x.subtract(BigInteger.ONE));
    }
    return res;
}

Greatest Common Divisor

$\gcd(x, y) = \gcd(x \bmod y, y)$

Modular Multiplicative Inverse

$\gcd(a, n) = 1$

$a\times{}b \equiv 1 (\bmod n)$

$a^{-1} \equiv b (\bmod n)$

$a^{-1} \equiv 1 \times{} a^{-1} \equiv a^{\phi(n)} \times{} a^{-1} \equiv a^{\phi(n) - 1} (\bmod n)$

Prime

质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个因数的数）。大于1的自然数若不是素数，则称之为合数。

public static boolean isPrime(BigInteger n) {
    BigInteger TWO = BigInteger.valueOf(2);
    BigInteger n_div_2 = n.divide(TWO);
    for (BigInteger i = TWO; i.compareTo(n_div_2) <= 0; i = i.add(BigInteger.ONE)) {
        if (n.mod(i).equals(BigInteger.ZERO)) {
            return false;
        }
    }
    return true;
}

Entropy