OpenSSH秘钥指纹图像生成算法

使用 SSH 秘钥生成时产生疑惑，它的 randomart image 是如何生成的？下面进行了探索和研究

引入

生成位数为 4096 位的 rsa 公私钥

ssh-keygen -t rsa -b 4096

Generating public/private rsa key pair.
Enter file in which to save the key (/root/.ssh/id_rsa):
Enter passphrase (empty for no passphrase):
Enter same passphrase again:
Your identification has been saved in /root/.ssh/id_rsa
Your public key has been saved in /root/.ssh/id_rsa.pub
The key fingerprint is:
SHA256:zUAZt7Ydw2s0LQqupcMjvB1KtniGX344tnxl2CE3zUg root@ArchLinux
The key's randomart image is:
+---[RSA 4096]----+
|        oo.      |
|       ...Eo .   |
|        o.o+B .  |
|       ..*==o*   |
|        S==o+    |
|   . . +. +.     |
|   .= O. o       |
|  .+oX++o        |
|  .+=.==         |
+----[SHA256]-----+

这张图到底是如何生成的？我十分好奇

算法

OpenSSH-5.1（2008）引入了这种指纹可视化方案
醉酒的主教（drunken bishop）
根据秘钥的指纹转换为字节流，从场地中心开始根据字节流向四周游走，记录每个像素途径的次数，根据次数进行打印

场地

定义场地宽为 17 个字符，高为 9 个字符，起点位于场地中心 (8, 4)

  01234567890123456
 +-----------------+ x
0|                 |
1|                 |
2|                 |
3|                 |
4|        S        |
5|                 |
6|                 |
7|                 |
8|                 |
 +-----------------+
 y

移动

以上面的秘钥指纹为例 SHA256:zUAZt7Ydw2s0LQqupcMjvB1KtniGX344tnxl2CE3zUg
首先通过 Base64 解码转换成 16进制 CD4019B7B61DC36B342D0AAEA5C323BC1D4AB678865F7E38B67C65D82137CD48
然后根据字节流进行拆分

Hex     |    C D    |    4 0    |    1 9    |    B 7    | ...
Bits    |11 00 11 01|01 00 00 00|00 01 10 01|10 11 01 11| ...
Steps   | 4  3  2  1| 8  7  6  5|12 11 10  9|16 15 14 13| ...

得到数组 ['01', '11', '00', '11', '00', '00', '00', '01', '01', '10', '01', '00', '11', '01', '11', '10', ...]

这个数组就是后续移动的步骤

定义移动方向 00 ↖ 01 ↗ 10 ↙ 11 ↘ （ 00 左上 01 右上 10 左下 11 右下 ）

打印

根据移动步骤移动后，每个像素就会有相应的经过次数，根据次数打印

起点(start) : S
终点(end) : E

每个值的对应规则：

次数：  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
字符：     .  o  +  =  *  B  O  X  @  %  &  #  /  ^  S  E  

 .o+=*BOX@%&#/^SE

代码实现

#!/usr/bin/env python

# NOTE: Requires Python 3+
# usage: drunken_bishop.py [-h] [--mode {md5,sha256}] fingerprint
#
# Generate randomart from fingerprint
#
# positional arguments:
#   fingerprint
#
# optional arguments:
#   -h, --help            show this help message and exit
#   --mode {md5,sha256}, -m {md5,sha256}

import argparse
import base64


def simulate_bishop_stumbles(steps):
    field = [[0] * 17 for _ in range(9)]
    start_position = (4, 8)
    direction_map = {
        "00": (-1, -1),
        "01": (-1, 1),
        "10": (1, -1),
        "11": (1, 1),
    }

    def clip_at_walls(x, y):
        return min(max(x, 0), 8), min(max(y, 0), 16)

    pos = start_position
    for step in steps:
        x, y = pos
        field[x][y] += 1
        dx, dy = direction_map[step]
        pos = clip_at_walls(x + dx, y + dy)

    x, y = start_position
    field[x][y] = 15
    x, y = pos
    field[x][y] = 16

    return field


def get_steps(fingerprint_bytes):
    return [
        "{:02b}".format(b >> s & 3) for b in fingerprint_bytes for s in (0, 2, 4, 6)
    ]


def print_randomart(atrium, hash_mode):
    # Symbols for the number of times a position is visited by the bishop
    # White space means that the position was never visited
    # S and E are the start and end positions
    value_symbols = " .o+=*BOX@%&#/^SE"

    print("+---[   n/a  ]----+")
    for row in atrium:
        symbolic_row = [value_symbols[visits] for visits in row]
        print("|" + "".join(symbolic_row) + "|")
    print("+" + ("[" + hash_mode.upper() + "]").center(17, "-") + "+")


def get_bytes(fingerprint, hash_mode):
    if hash_mode == "md5":
        return [int(i, 16) for i in fingerprint.split(":")]
    elif hash_mode == "sha256":
        missing_padding = 4 - (len(fingerprint) % 4)
        fingerprint += "=" * missing_padding
        return base64.b64decode(fingerprint)
    raise RuntimeError("Unsupported hashing mode: {}".format(hash_mode))


def get_argparser():
    parser = argparse.ArgumentParser(description="Generate randomart from fingerprint")
    parser.add_argument("--mode", "-m", choices=["md5", "sha256"], default="sha256")
    parser.add_argument("fingerprint", type=str)
    return parser


def drunken_bishop(fingerprint, hash_mode):
    fingerprint_bytes = get_bytes(fingerprint, hash_mode)
    steps = get_steps(fingerprint_bytes)
    atrium_state = simulate_bishop_stumbles(steps)
    print_randomart(atrium_state, hash_mode)


if __name__ == "__main__":
    parser = get_argparser()
    args = parser.parse_args()
    drunken_bishop(args.fingerprint, args.mode)

使用

python drunken_bishop.py --mode sha256 zUAZt7Ydw2s0LQqupcMjvB1KtniGX344tnxl2CE3zUg

+---[   n/a  ]----+
|        oo.      |
|       ...Eo .   |
|        o.o+B .  |
|       ..*==o*   |
|        S==o+    |
|   . . +. +.     |
|   .= O. o       |
|  .+oX++o        |
|  .+=.==         |
+-----[SHA256]----+

引用

openssh.com/txt/release-5.1 OpenSSH 5.1 更新日志
Making art with SSH key randomart GIF图片引用，算法解析
The drunken bishop: An analysis of the OpenSSH fingerprint visualization algorithm 算法解析，马尔科夫分析
A command to display a a key's randomart image from a fingerprint? - Stack Overflow 代码引用