NCPC2012G SHA-4
Problem G
SHA-4
Input File: pg.in
Time Limit: 3 seconds
This is a new hash algorithm invented for NCPC 2012, called SHA4 (simple hash algorithm version 4). Given a message string M, the SHA4 will hash the string into a 160 bits value, called the message digest d.
d = SHA4(M), where SHA4 is the hash function
We will give you the SHA4 algorithm and several hashed results of message digests: d0, d1, d2, …. You are to write a program to find the original message M0, M1, M2, …. Such that
d0 = SHA4(M0), d1 = SHA4(M1), d2 = SHA4(M2), …
Pseudocode for the SHA4 algorithm is listed in the following:
Note:
1. All variables are unsigned 32 bists integers.
2. The input string M is with length 5.
3. Each input character M[i] is converted into an integer value, by subtracting ASCII value of space from the ASCII value of M[i], that is, the difference between space and the character ASCII value. For example, the space value is 0.
4. After the value conversion, the five bytes values are stored in word[i], 0 <= i < 5.
Technical Specification
l The number of test cases is less the 1024.
l All output strings are with length 5.
輸入說明 ：
The first line of the input file contains an integer, denoting the number of test cases to follow. For each test case, the message hash digest is given with values of five 32 bits integer in hexadecimal format, each integer separated with at least one space. For example, a sample digest is 0b8414f6 027eeb13 0453edaf 00f93379 002f2d88. All digest values are valid SHA4 outputs.
輸出說明 ：
For each test case, output the original message with one line of string, containing only five alphanumeric characters (A-Za-z0-9). For example, you are to output ‘5dogs’ if the input is SHA4(‘5dogs’) = ‘0b8414f6 027eeb13 0453edaf 00f93379 002f2d88’.
範例輸入 ：
40b8414f6 027eeb13 0453edaf 00f93379 002f2d880b8419b0 027eec17 0453ef3f 00f933f1 002f2da80b8459a5 027efa02 045406ff 00f93981 002f2f100b845578 027ef91a 04540577 00f93921 002f2ef8
範例輸出 ：
5dogs9catsfade4cafe8
提示 ：
出處 ：
當下這題我們認為很難, 學長們甚至提出了全生成答案, 反正才 62^5, 之後使用資料壓縮字串塞到程式碼裡面上傳的牛逼算法。
但之後想說反正也不知道要做什麼, 就先本地展開方程式, 交給大學長, 看能不能推導結果, 之後發現直接反向依序代回即可, 方程式直接複製貼上就好, 連推導都不用呢。
當然我相信有更好的寫法。
#include <cstdio>
#include <iostream>
using namespace std;
int main() {
string a = "h0", b = "h1", c = "h2", d = "h3", e = "h4";
string f, tmp;
int i;
for(i = 0; i < 5; i++) {
f = b+ "+" +c;
char j = i+'0';
tmp = "4*(" + a + ")"+"+"+f+"+"+e+"+k"+"+word["+j+"]";
e = d, d = c, c = "8*(" + b + ")", b = a, a = tmp;
}
cout << "h0+"+a << endl<<endl;
cout << "h1+"+b << endl<<endl;
cout << "h2+"+c << endl<<endl;
cout << "h3+"+d << endl<<endl;
cout << "h4+"+e << endl<<endl;
return 0;
}
#include <stdio.h>
int main() {
int t, i;
unsigned int hh0, hh1, hh2, hh3, hh4;
unsigned int h0 = 0xdead, h1 = 0xcafe, h2 = 0xbeef, h3 = 0x3399, h4 = 0x7788, k = 0x5a82;
char buf[100], bt = 0;
for(i = '0'; i <= '9'; i++) buf[bt++] = i;
for(i = 'A'; i <= 'Z'; i++) buf[bt++] = i;
for(i = 'a'; i <= 'z'; i++) buf[bt++] = i;
scanf("%d", &t);
while(t--) {
scanf("%x %x %x %x %x", &hh0, &hh1, &hh2, &hh3, &hh4);
char word[5];
for(i = 0; i < bt; i++) {
word[0] = buf[i]-' ';
if(8*(4*(h0)+h1+h2+h4+k+word[0])+h4 == hh4)
break;
}
for(i = 0; i < bt; i++) {
word[1] = buf[i]-' ';
if(8*(4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1)+h3+k+word[1])+h3 == hh3)
break;
}
for(i = 0; i < bt; i++) {
word[2] = buf[i]-' ';
if(8*(4*(4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1)+h3+k+word[1])+4*(h0)
+h1+h2+h4+k+word[0]+8*(h0)+h2+k+word[2])+h2 == hh2)
break;
}
for(i = 0; i < bt; i++) {
word[3] = buf[i]-' ';
if(h1+4*(4*(4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1)+h3+k+word[1])+4*(h0)+h1+h2+h4+k+word[0]
+8*(h0)+h2+k+word[2])+4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1)+h3+k+word[1]+8*(4*(h0)
+h1+h2+h4+k+word[0])+8*(h1)+k+word[3] == hh1)
break;
}
for(i = 0; i < bt; i++) {
word[4] = buf[i]-' ';
if(h0+4*(4*(4*(4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1)+h3+k+word[1])+4*(h0)+h1+h2+h4+k+word[0]
+8*(h0)+h2+k+word[2])+4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1)+h3+k+word[1]+8*(4
*(h0)+h1+h2+h4+k+word[0])+8*(h1)+k+word[3])+4*(4*(4*(h0)+h1+h2+h4+k+word[0])+h0+8*(h1
)+h3+k+word[1])+4*(h0)+h1+h2+h4+k+word[0]+8*(h0)+h2+k+word[2]+8*(4*(4*(h0)+h1+h2+h4+k
+word[0])+h0+8*(h1)+h3+k+word[1])+8*(h0)+k+word[4] == hh0)
break;
}
for(i = 0; i < 5; i++)
printf("%c", word[i]+' ');
puts("");
}
return 0;
}
/*
4
0b8414f6 027eeb13 0453edaf 00f93379 002f2d88
0b8419b0 027eec17 0453ef3f 00f933f1 002f2da8
0b8459a5 027efa02 045406ff 00f93981 002f2f10
0b845578 027ef91a 04540577 00f93921 002f2ef8
*/