我最近一直在处理加密和哈希问题，我正试图通过使用文本来强行使用SHA-1。在编写了基本代码并确认它有效后，我想尝试提高它的效率，但我找不到太多需要提高效率的地方。所以，我做了我认为明智的事情：添加线程。
唯一的问题是，我找不到一个好的方法来实现它们，如果有的话。我尝试了一种实现，尽管使用的CPU功率几乎是单线程版本的3倍，但所用的时间是单线程版的10倍。
所以，如果你能看一看并给我一些建议，我将不胜感激。
单线程
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public int tim1;
void setup(){ //This is the main code block.
String input = "9e05e6832caffca519722b608570b8ff4935b94d"; //SHA-1 Hexadecimal Hash to be cracked
String chars = "abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789._!"; //Alphabet to use
int num = 7; //Maximum number of letters to try
tim1=millis(); //Starting timer
println(crack(input,chars,num)); //Cracking the input and outputting the result
println((millis()-tim1)/(float)1000); //Printing how long it took to crack.
}
//This function will take as input, a SHA-1 hash, an alphabet, and a maximum number of characters to test.
//It will either output the original string which converts to the hash, or "Unable to crack" if the given parameters do not lead to it.
String crack(String input, String chars, int num){
byte[] inp = hexStringToByteArray(input); //Converting the input to a byte array.
String output;
for(int i = 1; i<=num;i++){ //Bruteforce all passwords of length i, where i = 1 through num
output = bforce("",chars,i,inp);
if(output!=null){ //If the brute force algorithm outputs anything other than null, then the output is the cracked hash.
return output;
}
}
//If it returns null every time then either we didn't try enough characters, or it contained characters outside of our alphabet.
return "Unable to crack";
}
//This function will take as input, an intermediate string, an alphabet, a number of characters, and a sha-1 byte array to test against.
//It will test every combination of characters from the alphabet that can be added to the end intermediate string
//It only tests for a given length of num.
//To use the function on its own, you should simply provide an empty intermediate string.
//The function will either output null if it couldn't find the input that leads to the hash, or it will output the string that leads to the hash.
String bforce(String inter, String chars, int num,byte[] inp){
//This function will do pretty much all of the computations.
try{ //Try to run this code
String test; //String to be tested.
if(num-inter.length()==1){ //If the intermediate string contains all but one character, then run this code.
for(int i=0;i<chars.length();i++){ //For every character in the given alphabet
test=inter+chars.charAt(i); //Set the test string to the intermediate string + that character
if(bEquals(MessageDigest.getInstance("SHA-1").digest(test.getBytes()),inp)){ //Then convert that string into a SHA-1 Hash and see if it's equal to the input
return test; //If it is, then stop the code and return it.
} //Otherwise, keep going.
}
} else { //Otherwise, run this code.
for(int i=0;i<chars.length();i++){//For every character in the given alphabet
test=bforce(inter+chars.charAt(i),chars,num,inp);//Try every combination of letters after the intermediate string + that character
if(test!=null){//If one of their hashes is equal to the input byte array
return test; //Then stop the code and return it
} // Otherwise, keep going.
}
}
return null; //If the code is still running at this point, it means that we've tried every possibility.
} catch(NoSuchAlgorithmException e) { //If the code gives this specific type of error.
throw new RuntimeException(e); //Then stop the code and print the error.
}
}
//This function simply takes two byte arrays and outputs true if they're equal, or false if they're not.
boolean bEquals(byte[] x,byte[] y){
if(x.length!=y.length){ //If the lengths of the arrays aren't equal,
return false; //Then the arrays can't be equal, so return false and stop here.
} else { //Otherwise,
for(int i = 0;i<x.length;i++){//For every element in the first array
if(x[i]!=y[i]){//If it's not equal to the corresponding element in the second array,
return false;//Then return false and stop here.
}//Otherwise, keep going.
}
return true;//If the code is still running here, then it means that the arrays are equal, so return true.
}
}
//This function is not mine. I borrowed it off the internet, it simply takes a hexadecimal number in the form of a string, and converts it to a binary number in the form of a Byte array.
byte[] hexStringToByteArray(String s) {
int len = s.length();
byte[] data = new byte[len / 2];
for (int i = 0; i < len; i += 2) {
data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
+ Character.digit(s.charAt(i+1), 16));
}
return data;
}
多线程
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
public int tim1;
//Variables which will be used to pass data between threads
Thread thrd1;
Thread thrd2;
Thread thrd3;
MessageDigest msgdig1;
MessageDigest msgdig2;
MessageDigest msgdig3;
public int third1num1;
public int third2num1;
public int third3num1;
public int third1num2;
public int third2num2;
public int third3num2;
public String thread1output = null;
public String thread2output = null;
public String thread3output = null;
public String intermediate1;
public String intermediate2;
public String intermediate3;
public String alphabet1;
public String alphabet2;
public String alphabet3;
public byte[] inpt1;
public byte[] inpt2;
public byte[] inpt3;
void setup(){ //This is the main code block.
String input = "9e05e6832caffca519722b608570b8ff4935b94d"; //SHA-1 Hexadecimal Hash to be cracked
String chars = "abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789._!"; //Alphabet to use
int num = 5; //Maximum number of letters to try
tim1=millis(); //Starting timer
println(crack(input,chars,num)); //Cracking the input and outputting the result
println((millis()-tim1)/(float)1000); //Printing how long it took to crack.
}
//This function will take as input, a SHA-1 hash, an alphabet, and a maximum number of characters to test.
//It will either output the original string which converts to the hash, or "Unable to crack" if the given paramaters do not lead to it.
String crack(String input, String chars, int num){
byte[] inp = hexStringToByteArray(input); //Converting the input to a byte array.
String output;
for(int i = 1; i<=num;i++){ //Bruteforce all passwords of length i, where i = 1 through num
output = bforce("",chars,i,inp);
if(output!=null){ //If the brute force algorithm outputs anything other than null, then the output is the cracked hash.
return output;
}
}
//If it returns null every time then either we didn't try enough characters, or it contained characters outside of our alphabet.
return "Unable to crack";
}
//This function will take as input, an intermediate string, an alphabet, a number of characters, and a sha-1 byte array to test against.
//It will test every combination of characters from the alphabet that can be added to the end intermediate string
//It only tests for a given length of num.
//To use the function on its own, you should simply provide an empty intermediate string.
//The function will either output null if it couldn't find the input that leads to the hash, or it will output the string that leads to the hash.
String bforce(String inter, String chars, int num,byte[] inp){
//This function will do pretty much all of the computations.
if(inter.equals("aaaa")){println("aaaa");}
String test; //String to be tested.
if(inter.equals("")){
//Setting up the threads
thrd1 = new Thread(new thread1());
thrd2 = new Thread(new thread2());
thrd3 = new Thread(new thread3());
//Setting up Message digesters for threads
try{
msgdig1 = MessageDigest.getInstance("SHA-1");
msgdig2 = MessageDigest.getInstance("SHA-1");
msgdig3 = MessageDigest.getInstance("SHA-1");
} catch(NoSuchAlgorithmException e){
throw new RuntimeException(e);
}
//Dividing the alphabet into thirds for the threads to use.
println("mhm");
alphabet1 = chars;
alphabet2 = chars;
alphabet3 = chars;
third3num1 = chars.length();
third1num1 = third3num1/3;
third2num1 = third1num1*2;
third1num2 = third1num1;
third2num2 = third2num1;
third3num2 = third3num1;
//Setting the input for the threads to use
inpt3 = inp;
inpt2 = inp;
inpt1 = inp;
}
if(num-inter.length()==1){ //If the intermediate string contains all but one character, then run this code.
//Provide the intermediate for the threads to use
intermediate1=inter;
intermediate2=inter;
intermediate3=inter;
//Set up the threads
thrd1 = new Thread(new thread1());
thrd2 = new Thread(new thread2());
thrd3 = new Thread(new thread3());
//Run the threads
try{
thrd1.start();
thrd2.start();
thrd3.start();
} catch(Exception e){
println(thrd1.getState());
println(thrd2.getState());
println(thrd3.getState());
throw new RuntimeException(e);
}
//Wait for the other threads to finish
try{
thrd1.join();
thrd2.join();
thrd3.join();
} catch(Exception e) {
throw new RuntimeException(e);
}
if(thread1output!=null){ //If any of the threads found matching strings, then return them and stop the code.
return thread1output;
} else if (thread2output!=null){
return thread2output;
} else if (thread3output!=null){
return thread3output;
}
return null; //Otherwise, return null and stop the code.
} else { //Otherwise, run this code.
for(int i=0;i<chars.length();i++){//For every character in the given alphabet
test=bforce(inter+chars.charAt(i),chars,num,inp);//Try every combination of letters after the intermediate string + that character
if(test!=null){//If one of their hashes is equal to the input byte array
return test; //Then stop the code and return it
} // Otherwise, keep going.
}
}
return null; //If the code is still running at this point, it means that we've tried every possibility.
}
//These threads help spread the workload out across the CPU threads
public class thread1 implements Runnable {
public void run(){ //When this thread is started, run this code.
try { //Try to run this code
for(int i=0;i<third1num1;i++){//For every character in the first third of the alphabet
String test1=intermediate1+alphabet1.charAt(i);//Set the test string to the intermediate string + that character
if(bEquals(msgdig1.digest(test1.getBytes()),inpt1)){//Then convert that string into a SHA-1 Hash and see if it's equal to the input
thread1output=test1;//If it is, then stop the code and return it.
return;
} // Otherwise, keep going.
}
thread1output=null;//If none of the test strings' hashes are equivalent to the input, then set our output to null
return;
} catch (Exception e) { //If there's an error,
throw new RuntimeException(e); //Stop everything and print it.
}
}
}
public class thread2 implements Runnable {
public void run(){ //When this thread is started, run this code.
try { //Try to run this code
for(int i=third1num2;i<third2num1;i++){//For every character in the second third of the alphabet
String test2=intermediate2+alphabet2.charAt(i);//Set the test string to the intermediate string + that character
if(bEquals(msgdig2.digest(test2.getBytes()),inpt2)){//Then convert that string into a SHA-1 Hash and see if it's equal to the input
thread2output=test2;//If it is, then stop the code and return it.
return;
} // Otherwise, keep going.
}
thread2output=null;//If none of the test strings' hashes are equivalent to the input, then set our output to null
return;
} catch (Exception e) { //If there's an error,
throw new RuntimeException(e); //Stop everything and print it.
}
}
}
public class thread3 implements Runnable {
public void run(){ //When this thread is started, run this code.
try { //Try to run this code
for(int i=third2num2;i<third3num1;i++){//For every character in the final third of the alphabet
String test3=intermediate3+alphabet3.charAt(i);//Set the test string to the intermediate string + that character
if(bEquals(msgdig3.digest(test3.getBytes()),inpt3)){//Then convert that string into a SHA-1 Hash and see if it's equal to the input
thread3output=test3;//If it is, then stop the code and return it.
return;
} // Otherwise, keep going.
}
thread3output=null;//If none of the test strings' hashes are equivalent to the input, then set our output to null
return;
} catch (Exception e) { //If there's an error,
throw new RuntimeException(e); //Stop everything and print it.
}
}
}
//This function simply takes two byte arrays and outputs true if they're equal, or false if they're not.
boolean bEquals(byte[] x,byte[] y){
if(x.length!=y.length){ //If the lengths of the arrays aren't equal,
return false; //Then the arrays can't be equal, so return false and stop here.
} else { //Otherwise,
for(int i = 0;i<x.length;i++){//For every element in the first array
if(x[i]!=y[i]){//If it's not equal to the corresponding element in the second array,
return false;//Then return false and stop here.
}//Otherwise, keep going.
}
return true;//If the code is still running here, then it means that the arrays are equal, so return true.
}
}
//This function is not mine. I borrowed it off the internet, it simply takes a hexadecimal number in the form of a string, and converts it to a binary number in the form of a Byte array.
byte[] hexStringToByteArray(String s) {
int len = s.length();
byte[] data = new byte[len / 2];
for (int i = 0; i < len; i += 2) {
data[i / 2] = (byte) ((Character.digit(s.charAt(i), 16) << 4)
+ Character.digit(s.charAt(i+1), 16));
}
return data;
}
在这样一个计算量很大的任务中，CPU内核的数量直接限制了并行运行的任务数量。线程数量多于核心数量不会给您带来任何好处。
如果您只在递归的顶级中启动新线程，那么使用您现有的代码，我预计速度会提高3倍。线程之间没有任何依赖关系。通过在最后一级递归上启动新线程，可以创建数千个线程。创建和协调这些线程的开销远远大于并行运行的好处：
String bforce(String inter, String chars, int num,byte[] inp){
if(inter.equals("")){
// Start your 3 threads
} else if(num-inter.length()==1){
// DON'T start threads - use the existing logic you had
} else { //Otherwise, run this code.
// Recursive case
}
}
然而，这将限制您使用3个CPU核心，并且您仍然手动管理线程，这并不容易。最好使用高级别的API。
例如，您可以创建一个线程池，该线程池的线程数与CPU内核的线程数相同，然后为线程池创建并行运行的任务。这将确保您使用所有可用的CPU资源，并将开销降至最低。
// global scope
ExecutorService threadPool = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
// in "bforce"
if (inter.equals("")) {
// Create tasks to run in thread pool
List<Callable<String>> tasks = new ArrayList<>();
for (int i = 0; i < chars.length(); i++) {
String newInter = chars.substring(i, i + 1);
tasks.add(() -> bforce(newInter, chars, num, inp));
}
// Run all tasks in thread pool and wait for results
List<Future<String>> futures = threadPool.invokeAll(tasks);
// Inspect the results
for (Future<String> future : futures) {
String result = future.get();
// not sure what you want to do with this result...
}
}