哈希冲突_牛客题霸_牛客网

在密码学中，哈希碰撞是指找到两个不同的输入，使它们经过同一个哈希函数处理后得到相同的输出。在代码模板中给定了一个哈希函数 H，H 函数的实现如下： 1. 传入的参数，即加密前字符串 enc，会先与一个给定的密钥 key 拼接，得到字符串 key+enc（这里的加号代表字符串拼接）。 2. 对拼接后的字符串计算 SHA256 哈希值。 3. 取 SHA256 哈希值的前个字符作为结果。（本题中代表字符串 enc 的长度，即包含的字符个数。）你的任务是找到两个由小写字母组成的，且长度均为的不同的字符串，且它们经过 H 函数处理后得到相同的结果。

输入描述:

数据的输入部分已经完成，你只需要实现 solve() 函数即可。输入的数据可以通过全局变量的方式直接读取到。

输出描述:

求得对应的两个字符串后，把它们两个作为 solve() 函数的返回值即可。

示例1

输入

2
a

输出

mq ap

备注:

，，字符串 enc，key 中均只包含小写字母。

加载中...

import java.util.*;
import java.io.*;
import java.security.*;

public class Main {
    static class SHA256 {
        private static final long[] K = {
            0x428a2f98L, 0x71374491L, 0xb5c0fbcfL, 0xe9b5dba5L, 0x3956c25bL, 0x59f111f1L, 0x923f82a4L, 0xab1c5ed5L,
            0xd807aa98L, 0x12835b01L, 0x243185beL, 0x550c7dc3L, 0x72be5d74L, 0x80deb1feL, 0x9bdc06a7L, 0xc19bf174L,
            0xe49b69c1L, 0xefbe4786L, 0x0fc19dc6L, 0x240ca1ccL, 0x2de92c6fL, 0x4a7484aaL, 0x5cb0a9dcL, 0x76f988daL,
            0x983e5152L, 0xa831c66dL, 0xb00327c8L, 0xbf597fc7L, 0xc6e00bf3L, 0xd5a79147L, 0x06ca6351L, 0x14292967L,
            0x27b70a85L, 0x2e1b2138L, 0x4d2c6dfcL, 0x53380d13L, 0x650a7354L, 0x766a0abbL, 0x81c2c92eL, 0x92722c85L,
            0xa2bfe8a1L, 0xa81a664bL, 0xc24b8b70L, 0xc76c51a3L, 0xd192e819L, 0xd6990624L, 0xf40e3585L, 0x106aa070L,
            0x19a4c116L, 0x1e376c08L, 0x2748774cL, 0x34b0bcb5L, 0x391c0cb3L, 0x4ed8aa4aL, 0x5b9cca4fL, 0x682e6ff3L,
            0x748f82eeL, 0x78a5636fL, 0x84c87814L, 0x8cc70208L, 0x90befffaL, 0xa4506cebL, 0xbef9a3f7L, 0xc67178f2L
        };
        
        public static String hash(String input) {
            try {
                MessageDigest digest = MessageDigest.getInstance("SHA-256");
                byte[] hash = digest.digest(input.getBytes("UTF-8"));
                StringBuilder hexString = new StringBuilder();
                for (byte b : hash) {
                    String hex = Integer.toHexString(0xff & b);
                    if (hex.length() == 1) hexString.append('0');
                    hexString.append(hex);
                }
                return hexString.toString();
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
    }
    
    static int encLen;
    static String encKey;
    
    static String H(String str) {
        String combined = encKey + str;
        return SHA256.hash(combined).substring(0, encLen);
    }
    
    static class Pair<T, U> {
        T first;
        U second;
        
        Pair(T first, U second) {
            this.first = first;
            this.second = second;
        }
    }
    
    static Pair<String, String> solve() {
        // 在此处补全代码
        return new Pair<>("", "");
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        encLen = scanner.nextInt();
        encKey = scanner.next();
        
        Pair<String, String> result = solve();
        System.out.println(result.first + " " + result.second);
        
        scanner.close();
    }
}

#include <bits/stdc++.h>
using namespace std;
int enc_len;
string enc_key;

constexpr uint32_t SHA256_K[] = {
    0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
    0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
    0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
    0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
    0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
    0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
    0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
    0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
};

class SHA256 {
private:
    uint32_t m_h[8];
    std::vector<uint8_t> m_buffer;
    uint64_t m_bit_count;

static uint32_t rotr(uint32_t x, uint8_t n) { return (x >> n) | (x << (32 - n)); }
    static uint32_t ch(uint32_t e, uint32_t f, uint32_t g) { return (e & f) ^ (~e & g); }
    static uint32_t maj(uint32_t a, uint32_t b, uint32_t c) { return (a & b) ^ (a & c) ^ (b & c); }
    static uint32_t sigma0(uint32_t a) { return rotr(a, 2) ^ rotr(a, 13) ^ rotr(a, 22); }
    static uint32_t sigma1(uint32_t e) { return rotr(e, 6) ^ rotr(e, 11) ^ rotr(e, 25); }
    static uint32_t gamma0(uint32_t x) { return rotr(x, 7) ^ rotr(x, 18) ^ (x >> 3); }
    static uint32_t gamma1(uint32_t x) { return rotr(x, 17) ^ rotr(x, 19) ^ (x >> 10); }

void transform(const uint8_t* data) {
        uint32_t w[64];
        for (int i = 0; i < 16; ++i) {
            w[i] = static_cast<uint32_t>(data[i * 4 + 0]) << 24 |
                   static_cast<uint32_t>(data[i * 4 + 1]) << 16 |
                   static_cast<uint32_t>(data[i * 4 + 2]) << 8 |
                   static_cast<uint32_t>(data[i * 4 + 3]);
        }
        for (int i = 16; i < 64; ++i) {
            w[i] = gamma1(w[i - 2]) + w[i - 7] + gamma0(w[i - 15]) + w[i - 16];
        }

uint32_t a = m_h[0], b = m_h[1], c = m_h[2], d = m_h[3],
                 e = m_h[4], f = m_h[5], g = m_h[6], h = m_h[7];

for (int i = 0; i < 64; ++i) {
            uint32_t t1 = h + sigma1(e) + ch(e, f, g) + SHA256_K[i] + w[i];
            uint32_t t2 = sigma0(a) + maj(a, b, c);
            h = g; g = f; f = e; e = d + t1;
            d = c; c = b; b = a; a = t1 + t2;
        }

m_h[0] += a; m_h[1] += b; m_h[2] += c; m_h[3] += d;
        m_h[4] += e; m_h[5] += f; m_h[6] += g; m_h[7] += h;
    }

public:
    SHA256() {
        reset();
    }

void reset() {
        m_h[0] = 0x6a09e667; m_h[1] = 0xbb67ae85; m_h[2] = 0x3c6ef372; m_h[3] = 0xa54ff53a;
        m_h[4] = 0x510e527f; m_h[5] = 0x9b05688c; m_h[6] = 0x1f83d9ab; m_h[7] = 0x5be0cd19;
        m_bit_count = 0;
        m_buffer.clear();
    }

void update(const uint8_t* data, size_t len) {
        for (size_t i = 0; i < len; ++i) {
            m_buffer.push_back(data[i]);
            if (m_buffer.size() == 64) {
                transform(m_buffer.data());
                m_bit_count += 512;
                m_buffer.clear();
            }
        }
    }

vector<uint8_t> digest() {
        vector<uint8_t> final_buffer(m_buffer);
        m_bit_count += m_buffer.size() * 8;

final_buffer.push_back(0x80);
        while (final_buffer.size() % 64 != 56) {
            final_buffer.push_back(0x00);
        }

for (int i = 7; i >= 0; --i) {
            final_buffer.push_back(static_cast<uint8_t>((m_bit_count >> (8 * i)) & 0xFF));
        }

for (size_t i = 0; i < final_buffer.size(); i += 64) {
            transform(&final_buffer[i]);
        }

vector<uint8_t> hash(32);
        for (int i = 0; i < 8; ++i) {
            hash[i * 4 + 0] = static_cast<uint8_t>((m_h[i] >> 24) & 0xFF);
            hash[i * 4 + 1] = static_cast<uint8_t>((m_h[i] >> 16) & 0xFF);
            hash[i * 4 + 2] = static_cast<uint8_t>((m_h[i] >> 8) & 0xFF);
            hash[i * 4 + 3] = static_cast<uint8_t>(m_h[i] & 0xFF);
        }

reset();
        return hash;
    }
};

string H(string enc) {
    // 1. 拼接 key + enc
    string input = enc_key + enc;

// 2. 计算 SHA256 哈希
    SHA256 sha;
    sha.update(reinterpret_cast<const uint8_t*>(input.data()), input.size());
    vector<uint8_t> hash_bytes = sha.digest();

// 3. 转为十六进制字符串
    stringstream ss;
    for (uint8_t byte : hash_bytes) {
        ss << std::hex << std::setw(2) << std::setfill('0') << static_cast<int>(byte);
    }
    std::string hex_hash = ss.str();

// 4. 取前 |enc| 个字符
    return hex_hash.substr(0, enc_len);
}

pair<string, string> solve() {
    //此处补全代码
}

int main() {
    cin >> enc_len >> enc_key;
    auto result = solve();
    cout << result.first << " " << result.second << endl;
    return 0;
}