Algorithm optimization in the enigma app

Message boards : Number crunching : Algorithm optimization in the enigma app

To post messages, you must log in.

AuthorMessage
Alex VE3NEA

Send message
Joined: 22 Oct 16
Posts: 17
Credit: 17,095
RAC: 259
Message 4143 - Posted: 23 Oct 2016, 1:09:45 UTC

Hello,

Here is my attempt to improve the hill climbing algorithm used in the enigma app.

Hill climbing finds the plugboard connections by trying every possible way of re-connecting the letters, scoring the decrypted text, and retaining the modifications that improve the score. Some modifications that the program tries have a very small probability of improving the solution, and some others are tried twice during the same pass. Elimination of the inefficient and redundant modifications dramatically improves the speed: the modified program makes three quick passes in the time of a single slow one, and the chances of finding the solution significantly increase.

The new algorithm was tested on 1000 messages, randomly selected from a text in German and encrypted with random M3 Enigma settings. The n-gram dictionaries were generated from the same text.

Here is a plot of the success rate of solving the plugboard vs. the time spent on each plugboard. The new algorithm performs better than the original hill climbing at all message lengths.





The plotted data in the tabluar form are here (sorry, I am not allowed to post url's here):

http://www.dxatlas.com/DxMath/Enigma/EnigmaSpeed.txt


The new executable for Windows is here for you to try:

http://www.dxatlas.com/DxMath/Enigma/EnigmaProject.exe.zip

Note that this program requires a unigram dictionary (included).


The source code of the modified enigma, (compiles in Visual Studio 2015), the testing application, and the test data are here:

http://www.dxatlas.com/DxMath/Enigma/EnigmaSolution.src.zip


Cheers,

Alex
ID: 4143 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
jj666

Send message
Joined: 10 Mar 14
Posts: 8
Credit: 68,796,111
RAC: 0
Message 4158 - Posted: 6 Nov 2016, 0:26:07 UTC - in response to Message 4143.  

Hello there,

Currently using Agbar's optimised binary. I notice with this release, there are no app_info.xml or wrapper.exe.

What's the correct procedure for installation/testing?

Cheers,

-jj-
ID: 4158 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
oh2hyt

Send message
Joined: 14 Jul 09
Posts: 33
Credit: 23,742,934
RAC: 32,000
Message 4162 - Posted: 6 Nov 2016, 17:44:24 UTC
Last modified: 6 Nov 2016, 17:46:17 UTC

I think we should get TJM's approve before using this for Enigma@Home as this version gives different results than other so far optimized executables. This is logical, because this use different algorithm.

I tried already contact TJM, but no repply.

Speedwise this would be -60% computation time compared optima avx2, BUT this one doesn't achieve as high scores always.
ID: 4162 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
Alex VE3NEA

Send message
Joined: 22 Oct 16
Posts: 17
Credit: 17,095
RAC: 259
Message 4171 - Posted: 10 Nov 2016, 22:48:14 UTC - in response to Message 4158.  

This program is only for testing and for stand-alone execution, not for the enigma@home work yet. It will likely need a different work unit type since it works with unigrams instead of bigrams, and requires a different number of passes.

Alex
ID: 4171 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
Profile TJM
Volunteer moderator
Project administrator
Project developer
Project scientist
Avatar

Send message
Joined: 25 Aug 07
Posts: 734
Credit: 21,968,210
RAC: 17,952
Message 4460 - Posted: 26 Apr 2017, 13:56:47 UTC

I'm going to test this app against a set of test files. After upcoming server upgrade it might be possible to add it as a second application with it's own workunit set.

M4 Project homepage
M4 Project wiki
ID: 4460 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
Profile TJM
Volunteer moderator
Project administrator
Project developer
Project scientist
Avatar

Send message
Joined: 25 Aug 07
Posts: 734
Credit: 21,968,210
RAC: 17,952
Message 4617 - Posted: 5 May 2017, 7:28:41 UTC - in response to Message 4460.  

So I ran series of tests against real M4 messages truncated to 72 letters.

The app is much faster than standard version, however in some scenarios it also requires significantly more walks over the same keyrange to find the solution. On the other hand, some of the tests which are hard to break with the standard app, this one breaks more easily with less restarts.

I used "U534 version 1" dictionary set which was generated from real messages, with the unidict generated from the same plaintexts.

I'm going to add it as a second app. It was scheduled for this weekend but the company that hosts my front end server has some technical problems (as you might have noticed the server was unreachable most of the time during past few days) so probably there will be a delay.

The biggest challenge is to get the work generator (the thing that automatically splits keyrange into workunits and inserts them into BOINC) patched so it could run two or more different app at once. I have already started working on this and perhaps it will be done in a few days.
M4 Project homepage
M4 Project wiki
ID: 4617 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
oh2hyt

Send message
Joined: 14 Jul 09
Posts: 33
Credit: 23,742,934
RAC: 32,000
Message 4848 - Posted: 15 May 2017, 16:51:50 UTC

I assume this is Enigma AV -application on boinc project.

Could someone port this also to linux?
ID: 4848 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
Tom_unoduetre

Send message
Joined: 18 Sep 07
Posts: 10
Credit: 153,039
RAC: 98
Message 4882 - Posted: 16 May 2017, 12:58:48 UTC

I´m currently using an app_info.xml so I can run the optimized app from here: http://www.enigmaathome.net/forum_thread.php?id=281#2213

How can I get the AV app? I cannot select it in the project preferences.
ID: 4882 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
Agbar

Send message
Joined: 10 Sep 09
Posts: 19
Credit: 568,278
RAC: 866
Message 4896 - Posted: 18 May 2017, 20:00:59 UTC - in response to Message 4882.  
Last modified: 18 May 2017, 20:01:11 UTC

To configure app_info.xml please follow http://boinc.berkeley.edu/wiki/Anonymous_platform.
ID: 4896 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote
Profile TJM
Volunteer moderator
Project administrator
Project developer
Project scientist
Avatar

Send message
Joined: 25 Aug 07
Posts: 734
Credit: 21,968,210
RAC: 17,952
Message 4916 - Posted: 21 May 2017, 15:00:36 UTC - in response to Message 4896.  
Last modified: 21 May 2017, 15:04:39 UTC

To run both apps you need app_info like this one:

<app_info>
   <app>
      <name>enigma_m4_2</name>
      <user_friendly_name>Enigma 0.76b-Opt</user_friendly_name>
   </app>
   <app>
      <name>enigma_m4_3</name>
      <user_friendly_name>Enigma AV</user_friendly_name>
   </app>
   <file_info>
      <name>wrapper_5.22_windows_intelx86.exe</name>
      <executable/>
   </file_info>
   <file_info>
       <name>enigma_0.76_windows_intelx86.exe</name>
       <executable/>
   </file_info>
   <file_info>
       <name>job_1.22.xml</name>
   </file_info>
  <file_info>
      <name>wrapper_1.05_windows_x86_64.exe</name>
      <executable/>
   </file_info>
   <file_info>
       <name>enigma3_1.05_windows_x86_64.exe</name>
       <executable/>
   </file_info>
   <file_info>
       <name>job_1.51.xml</name>
   </file_info>
   
   <app_version>
      <app_name>enigma_m4_2</app_name>
      <version_num>522</version_num>
      <file_ref>
         <file_name>wrapper_5.22_windows_intelx86.exe</file_name>
         <main_program/>
      </file_ref>
      <file_ref>
        <file_name>enigma_0.76_windows_intelx86.exe</file_name>
	<open_name>enigma2_0.76_windows_intelx86.exe</open_name>
      </file_ref>
      <file_ref>
         <file_name>job_1.22.xml</file_name>
         <open_name>job.xml</open_name>
      </file_ref>
   </app_version>
 
   <app_version>
      <app_name>enigma_m4_3</app_name>
      <version_num>105</version_num>
      <file_ref>
         <file_name>wrapper_1.05_windows_x86_64.exe</file_name>
         <main_program/>
      </file_ref>
      <file_ref>
        <file_name>enigma3_1.05_windows_x86_64.exe</file_name>
	<open_name>enigma_av.exe</open_name>
      </file_ref>
      <file_ref>
         <file_name>job_1.51.xml</file_name>
         <open_name>job.xml</open_name>
      </file_ref>
   </app_version>
</app_info>


executables and job file can be downloaded from:
http://download.enigmaathome.net/enigma3_1.05_windows_x86_64.exe
http://download.enigmaathome.net/wrapper_1.05_windows_x86_64.exe
http://download.enigmaathome.net/job_1.51.xml

or if you need 32bit version, replace windows_x86_64 with windows_intelx86 in both app_info and download links.

intelx86 version requires 32bit 686 CPU.
x86_64 version requires 64bit CPU with SSE2. It's up to 15% faster.
M4 Project homepage
M4 Project wiki
ID: 4916 · Rating: 0 · rate: Rate + / Rate - Report as offensive    Reply Quote

Message boards : Number crunching : Algorithm optimization in the enigma app




Copyright © 2017 TJM