1

160 位 SHA1 的所有转换都使用 40 个 ascii 字符(320 位)来表示 160 位数据(我已经能够找到)。我需要对此进行优化并使用尽可能少的 ascii 字符来表示 SHA1 哈希。

例如,当通过典型算法转换时,这个字符串“The quick brown fox jumps over the lazy dog”在 ASCII“2FD4E1C67A2D28FCED849EE1BB76E7391B93EB12”中等于这个字符串。

我创建了一个算法,每个 ASCII 字符使用 5 位,所以我需要 40 个 ASCII 字符到 32 个“F0K1032QD08C1M44U11B0R77P3R31L2I”。

有没有人有更好的方法来获得更少的字符,但不会丢失信息(通过有损压缩技术或使用像 MD5 这样的更小的散列)?我需要将此哈希表示为 Windows 上的文件夹,因此无法使用大写和小写字母来使用每个字符 6 位。

class Program
{
    static byte[] GetBytesForTypical(byte[] hash)
    {
        List<byte> newHash = new List<byte>();

        foreach (byte b in hash)
        {
            int first4Bits = (b & 0xF0) >> 4;
            int last4bits = b & 0x0F;

            newHash.Add((byte)first4Bits);
            newHash.Add((byte)last4bits);
        }

        return newHash.ToArray();
    }

    public static string ConvertHashToFileSystemFriendlyStringTypical(byte[] str)
    {
        StringBuilder strToConvert = new StringBuilder();

        foreach (byte b in str)
        {
            strToConvert.Append(b.ToString("X"));
        }

        return strToConvert.ToString();
    }

    static byte[] GetBytesForCompressedAttempt(byte[] hash)
    {
        byte[] newHash = new byte[32];

        // the bit array 5 bits at a time
        // at 8 bits per bytes that is 40 bits per loop 4 times
        int byteCounter =0;
        int k = 0;
        for(int i=0; i < 4 ;++i)
        {
            //Get 5 bits worth
            newHash[k] = (byte)(hash[byteCounter] & 0x1F);
            hash[byteCounter] >>= 5;
            ++k;

            //Get 3 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x7);
            newHash[k] <<= 2;
            ++byteCounter;

            // get 2 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x3);
            ++k;

            // get 5 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x1F);
            hash[byteCounter] >>= 5;
            ++k;

            // get 1 bit
            newHash[k] = (byte)(hash[byteCounter] & 0x1);
            newHash[k] <<= 7;
            ++byteCounter;

            // get 4 bits
            newHash[k] = (byte)(hash[byteCounter] & 0xF);
            ++k;
            hash[byteCounter] >>= 4;

            // get 4 bits
            newHash[k] = (byte)(hash[byteCounter] & 0xF);
            ++byteCounter;

            // get 1 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x1);
            hash[byteCounter] >>=1;
            ++k;

            // get 5 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x1F);
            ++k;
            hash[byteCounter] >>= 5;

            // get 2 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x3);
            ++byteCounter;

            // get 3 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x7);
            ++k;

            // get 5 bits
            newHash[k] = (byte)(hash[byteCounter] & 0x1F);
            ++byteCounter;
            ++k;

        }

        return newHash;
    }

    public static string ConvertHashToFileSystemFriendlyStringCompressedl(byte[] str)
    {
        StringBuilder strToConvert = new StringBuilder();

        foreach (byte b in str)
        {
            System.Diagnostics.Debug.Assert(b < 32);

            if (b >= 10 && b < 32)
            {
                strToConvert.Append((char)(b - 10 + 'A'));
            }
            else
            {
                strToConvert.Append((char)(b + '0'));
            }
        }

        return strToConvert.ToString();
    }

    static void Main(string[] args)
    {
        System.Security.Cryptography.SHA1 hasher = System.Security.Cryptography.SHA1.Create();

        byte[] data = hasher.ComputeHash(Encoding.Default.GetBytes("The quick brown fox jumps over the lazy dog"));
        byte[] stringBytesTypical = GetBytesForTypical(data);
        string typicalFriendlyHashString = ConvertHashToFileSystemFriendlyStringTypical(stringBytesTypical);
        //2FD4E1C67A2D28FCED849EE1BB76E7391B93EB12 == typicalFriendlyHashString

        byte[] stringBytesCompressedAttempt = GetBytesForCompressedAttempt(data);
        string compressedFriendlyHashString = ConvertHashToFileSystemFriendlyStringCompressedl(stringBytesCompressedAttempt);
        //F0K1032QD08C1M44U11B0R77P3R31L2I == compressedFriendlyHashString

    }
}

编辑:需要减少到少于 40 个字符与 Windows 文件夹名称无关。(尽管它可能因为 Windows 路径有限制)。我需要为人类可读的字符串保留尽可能多的空间,然后为需要查看的任何内容创建一个文件夹。40 个字符的 ascii 字符串的问题是 1/2 位被设置为 0 并且本质上是浪费的。因此,当存储数以百万计的哈希空间和查找速度开始变得交织在一起。我无法重新设计用户工作流程,但我可以让系统更加灵活并消耗更少的内存

编辑:这也将改善用户体验。目前,用户必须使用部分散列来查找内容。更糟糕的情况(在实践中)当前需要使用散列中的前 8 个字符,以确保没有重复。这 8 个字符代表 32 位的真实哈希数据。降低到每个字符 5 位用户将只需要 6 个字符来确保没有重复。如果我能得到 6 位,那么用户应该只需要大约 5 个字符。这进入了大多数人能够记住的领域

编辑:我从上面提出的原始代码中取得了一些进展。一旦我将散列转换为十六进制(基数 36),我就能够从上面的原始 5 位实现中删除其中一个字符。所以我目前有 31 个字符。这意味着从检索需要 8 个字符的典型实现(在实践中)用户应该能够使用 6 个字符来检索相同的数据。

public static string ConvertHashToFileSystemFriendlyStringCompressed2(byte[] hashData)
        {
            string mapping = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

            BigInteger base10 = new BigInteger(hashData);
            string base36;
            var result = new Stack<char>();

            do
            {
                result.Push(mapping[(int)(base10 % 36)]);
                base10 /= 36;

            } while (base10 != 0);

            base36 = new string(result.ToArray());

            return base36;
        }

编辑:一直在做更多的研究,我想发布一张图表,显示随着您必须选择的 ASCII 字符数量的增加,您获得的收益递减。你最终需要越来越多的角色来获得越来越小的收益。我似乎处于您获得最大收益的尾端(36 个字符)。因此,即使我能够跳转到使用 64 个字符(目前我不能),我也只删除了最终字符串中的 4 个。但是,如果将原始散列缩小到 18 个字节,那么相同的 36 个字符现在只会创建一个 27 个字符的字符串(与转换为 base 64 的长度相同)。现在的问题是如何可靠地将 20 字节的哈希压缩成 18 字节。截断不起作用,因为如果我使用截断,用户仍然需要记住 6 个字符。

在此处输入图像描述

在此处输入图像描述

编辑:所以我压缩哈希字节的尝试没有成功。我预料到了这一点,但不得不尝试向自己证明这一点。基本上我所做的是尝试使用霍夫曼代码来压缩原始哈希。

由于散列中的每个值都同样可能(良好散列的定义)使用通用霍夫曼树进行所有压缩是不可能的(因为这会产生相同数量的比特,我试图压缩而没有净收益)。但是,一旦您为特定散列创建了 Huffman 树,您确实会压缩原始散列(例如 20 字节到 16 字节),但随后会丢失保存的 4 个字节,因为您还必须存储 Huffman 树。这种方法可能适用于更长的散列值(512 位等),但对于所有 SHA1 散列值来说似乎不能很好地保证实施(只有非常小的 SHA1 散列输出子集将从这种类型的压缩中受益)。

4

0 回答 0