Ç - 隐窝() - 代码需要更长的时间,用5环或多于4个环,但使用相同的参数/散列
我正在称为CS50的EDX当然执行。也许你们有些人很熟悉它。Ç - 隐窝() - 代码需要更长的时间,用5环或多于4个环,但使用相同的参数/散列
一个设置问题,请您实现一个算法破解这是使用DES为基础的加密散列和高达4个字符的密码。
到目前为止,这么好。我已经完成了。
但我还是决定提高一点点,并有可能破解是最多8个字符,这是基于DES加密的密码最大。
而问题是,当我添加了第五个字符(或更多)的可能性,我的代码不工作了。
这里是我的代码
这一个工作:
#define _XOPEN_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <string.h>
/*
Use this to compile
clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wshadow crack4.c -lcrypt -lm -o crack4
*/
int main(int argc, char *argv[])
{
if (argc != 2) //Checks if number of command-line arguments is valid
{
printf ("usage: ./crack + hash \n");
return 1; //Retuns 1 (error)
}
char *hash = argv[1]; //Gets hash passed as argument
char salt[3]; //Gets the salt
salt[0] = hash[0];
salt[1] = hash[1];
salt[2] = '\0';
//All possible characters used in a DES-based hashed password (taken from gnu library)
const char *const seedchars = " ./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
char text[9] = "\0"; //Text that is gonna be tried with crypt()
for (int d = 0; d <= 64 ; d++) //To check for passwords of up to 4 characters
{
printf("d %d \n", d);
if(d > 0)
{
text[4] = '\0'; //Defining null-terminator at index 4
text[3] = seedchars[d]; //Iterates through the seedchars list at index 3
}
for (int c = 0; c <= 64 ; c++) //To check for passwords of up to 3 characters
{
if(c > 0)
{
if (d == 0)
{
text[3] = '\0'; //Defining null-terminator at index 3
}
text[2] = seedchars[c]; //Iterates through the seedchars list at index 2
}
for (int b = 0; b <= 64 ; b++) //To check for passwords of up to 2 characters
{
if(b > 0)
{
if (c == 0 && d == 0)
{
text[2] = '\0'; //Defining null-terminator at index 2
}
text[1] = seedchars[b]; //Iterates through the seedchars list at index 1
}
for (int a = 0; a <= 64 ; a++) //To check for passwords of up to 1 character
{
if(b == 0 && c == 0 && d == 0)
{
text[1] = '\0'; //Defining null-terminator at index 1
}
text[0] = seedchars[a]; //Iterates through the seedchars list at index 0
char *password = crypt(text, salt); //Hash var text and save it to var password
if (strcmp(hash, password) == 0) //Compares the hash passed as argv with created above
{
printf("%s\n", text); //prints the text that led to said hash
return 0; //Returns 0 (okay)
}
}
}
}
}
return 1; //Retuns 1 (error)
}
这一个不工作:
#define _XOPEN_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <string.h>
/*
Use this to compile
clang -ggdb3 -O0 -std=c11 -Wall -Werror -Wshadow crack.c -lcrypt -lm -o crack
*/
int main(int argc, char *argv[])
{
if (argc != 2) //Checks if number of command-line arguments is valid
{
printf ("usage: ./crack + hash \n");
return 1; //Retuns 1 (error)
}
char *hash = argv[1]; //Gets hash passed as argument
char salt[3]; //Gets the salt
salt[0] = hash[0];
salt[1] = hash[1];
salt[2] = '\0';
//All possible characters used in a DES-based hashed password (taken from gnu library)
const char *const seedchars = "./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
char text[9] = "\0"; //Text that is gonna be tried with crypt()
for (int h = 0; h <= 64 ; h++) //To check for passwords of up to 8 characters
{
if(h > 0)
{
text[8] = '\0'; //Defining null-terminator at index 8
text[7] = seedchars[h]; //Iterates through the seedchars list at index 7
}
for (int g = 0; g <= 64 ; g++) //To check for passwords of up to 7 characters
{
if(g > 0)
{
if (h == 0)
{
text[7] = '\0'; //Defining null-terminator at index 7
}
text[6] = seedchars[g]; //Iterates through the seedchars list at index 6
}
for (int f = 0; f <= 64 ; f++) //To check for passwords of up to 6 characters
{
if(f > 0)
{
if (g == 0 && h == 0)
{
text[6] = '\0'; //Defining null-terminator at index 6
}
text[5] = seedchars[f]; //Iterates through the seedchars list at index 5
}
for (int e = 0; e <= 64 ; e++) //To check for passwords of up to 5 characters
{
if(e > 0)
{
if (f == 0 && g == 0 && h == 0)
{
text[5] = '\0'; //Defining null-terminator at index 5
}
text[4] = seedchars[e]; //Iterates through the seedchars list at index 4
for (int d = 0; d <= 64 ; d++) //To check for passwords of up to 4 characters
{
printf("d %d \n", d);
if(d > 0)
{
if (e == 0 && f == 0 && g == 0 && h == 0)
{
text[4] = '\0'; //Defining null-terminator at index 4
}
text[3] = seedchars[d]; //Iterates through the seedchars list at index 3
}
for (int c = 0; c <= 64 ; c++) //To check for passwords of up to 3 characters
{
if(c > 0)
{
if (d == 0 && e == 0 && f == 0 && g == 0 && h == 0)
{
text[3] = '\0'; //Defining null-terminator at index 3
}
text[2] = seedchars[c]; //Iterates through the seedchars list at index 2
}
for (int b = 0; b <= 64 ; b++) //To check for passwords of up to 2 characters
{
if(b > 0)
{
if (c == 0 && d == 0 && e == 0 && f == 0 && g == 0 && h == 0)
{
text[2] = '\0'; //Defining null-terminator at index 2
}
text[1] = seedchars[b]; //Iterates through the seedchars list at index 1
}
for (int a = 0; a <= 64 ; a++) //To check for passwords of up to 1 character
{
if(b == 0 && c == 0 && d == 0 && e == 0 && f == 0 && g == 0 && h == 0)
{
text[1] = '\0'; //Defining null-terminator at index 1
}
text[0] = seedchars[a]; //Iterates through the seedchars list at index 0
char *password = crypt(text, salt); //Hash var text and save it to var password
if (strcmp(hash, password) == 0) //Compares the hash passed as argv with created above
{
printf("%s\n", text); //prints the text that led to said hash
return 0; //Returns 0 (okay)
}
}
}
}
}
}
}
}
}
}
return 1; //Retuns 1 (error)
}
我在这两个代码使用下面的哈希值,但它不适用于第二个代码。
hash - 50fkUxYHbnXGw
text - rofl
有人可以帮我理解为什么它不工作?
谢谢。
编辑:
第二个代码刚刚结束运行,它实际上是工作,但它采取的方式更长的时间来破解密码。下面是截图:
我不能够将它张贴作为某些原因图像,所以这里的链接http://imgur.com/a/GVWar
编辑2:添加链接的图像和固定标题
编辑3:重新修复标题
在第一种情况下,对于4个字符,您有4个嵌套循环。哪个“for”将执行多达64次。所以你的代码可能运行64^4 = 1600万次。
在第二种情况下,对于8个字符,您有8个嵌套循环。这使得64^8 = 281万亿次。
您的计算机需要执行algoritm的时间是成正比的循环量。
它长得很快,因为你的算法是对的字符数指数。如果您想了解更多信息,请搜索“算法渐近表示法”。
我得到它应该需要更长的时间来执行,因为它是8个嵌套循环而不是4个。 但问题是,就像我张贴的图片中所示,在第一个代码中,d(第四个循环)上升到50,然后它会破解密码。而在第二个代码中,e(第5个循环)上升到64,这意味着之前的循环运行64^2 = 128次。 编辑:添加信息。 –
为了使它更清楚,你可以在内部循环(for(int a ...))内部添加“printf”波纹管,以输出每一步。 a)(a)(b)(b)(a)d) ;” 如果这需要太长时间才能运行,请添加一个简单的计数器(如“total ++;”)并在最后打印一次。将“total”声明为** long ** int。 –
我已经做到了。但是,只能分别在d循环和8循环代码中打印d和e。这就是那张照片来自哪里,我知道如何解决相同的散列需要更长的时间。 –
您可以将a-h视为由65个字符组成的*,索引为0到64.最后一个字符是声明值的行终止符。
如果您要添加一个printf的e值:
crack08 50fkUxYHbnXGw
e 1
d 0
d 1
d 2
d 3
d 4
d 5
d 6
d 7
d 8
d 9
d 10
d 11
d 12
d 13
d 14
d 15
d 16
d 17
d 18
d 19
d 20
d 21
d 22
d 23
...
d 63
d 64
e 2
d 0
d 1
d 2
...
你会看到我们会在e的第一个值跳过,因为^ h - f为0
查找然后将4个字符的匹配推迟到e = 64(第65个索引'\ 0'字符串终止符)。
在查找4个字符的密码之前,这代表了超过65倍的时间。
摆脱额外过程包括重新组织所用字符的“*”,添加'\ 0'字符作为第一个字符,将其作为第一个字符串的字符串终止符并跳过它以供后续传递:
#define _XOPEN_SOURCE
#include <stdio.h>
#include <unistd.h>
#include <string.h>
int main(int argc, char *argv[])
{
if (argc != 2) {
printf ("usage: ./crack hash\n");
return 1; //Retuns 1 (error)
}
char *hash = argv[1];
char salt[3];
salt[0] = hash[0];
salt[1] = hash[1];
salt[2] = '\0';
# define WHEEL_SIZE 65 // all possible password characters
// plus null character for shorter strings
char seedchars[WHEEL_SIZE] =
"@./ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
char text[9]; // Text that is gonna be tried with crypt()
text[8] = '\0'; // for h > 0
seedchars[0] = '\0'; // test for short strings first
int a_first = 0;
int b_first = 0;
int c_first = 0;
int d_first = 0;
int e_first = 0;
int f_first = 0;
int g_first = 0;
for (int h = 0; h <= WHEEL_SIZE - 1 ; h++) {
text[7] = seedchars[h];
for (int g = g_first ; g <= WHEEL_SIZE - 1; g++) {
text[6] = seedchars[g];
for (int f = f_first; f <= WHEEL_SIZE -1; f++) {
text[5] = seedchars[f];
for (int e = e_first; e <= WHEEL_SIZE - 1; e++) {
printf("e %2d\n", e);
text[4] = seedchars[e];
for (int d = d_first; d <= WHEEL_SIZE - 1; d++) {
printf("d %2d\n", d);
text[3] = seedchars[d];
for (int c = c_first; c <= WHEEL_SIZE - 1; c++) {
if (c > 0)
b_first = 1;
text[2] = seedchars[c];
for (int b = b_first; b <= WHEEL_SIZE - 1; b++) {
text[1] = seedchars[b];
for (int a = a_first; a <= WHEEL_SIZE - 1; a++) {
text[0] = seedchars[a];
char *password = crypt(text, salt);
if (strcmp(hash, password) == 0) {
printf("%s\n", text);
return 0;
}
}
b_first = 1;
}
c_first = 1;
}
c_first = 1;
}
d_first = 1;
}
e_first = 1;
}
f_first = 1;
}
g_first = 1;
}
return 1;
}
这给了我们答案在最短的时间:
crack 50fkUxYHbnXGw
e 0
d 0
d 1
d 2
d 3
d 4
d 5
d 6
d 7
d 8
d 9
d 10
d 11
d 12
d 13
d 14
d 15
d 16
d 17
d 18
d 19
d 20
d 21
d 22
d 23
d 24
d 25
d 26
d 27
d 28
d 29
d 30
d 31
d 32
d 33
d 34
d 35
d 36
d 37
d 38
d 39
d 40
d 41
d 42
d 43
d 44
d 45
d 46
d 47
d 48
d 49
d 50
rofl
一个更满意的答案。
对不起,但“不工作”不是一个有用的问题描述。它也不适合像SO这样的问答网站。 – StoryTeller
“它不起作用。为什么它不工作”....“它实际上是在工作”......可能应该编辑你的问题,只是说出问题是什么,而不是混淆。 – kaylum
修复你的标题:你的代码有效,所以你真正的问题是为什么它需要这么长时间。法比奥回答如下。 – TheGreatContini