We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. All Contests
  2. ProjectEuler+
  3. Project Euler #59: XOR decryption
  4. Discussions

Project Euler #59: XOR decryption

Sort by

recency

|

24 Discussions

|

  • ketan_patel25
     + 0 comments

    JAva code

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

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
     List<Integer> ascii = new ArrayList<>();
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0; i<n; i++)
            ascii.add(sc.nextInt());
        sc.close();
        
        Map<Integer, Integer> freq = new HashMap<>();
        StringBuilder key = new StringBuilder();
        
        for(int i=0, time=0;; i+=3){
            if(i>=ascii.size()){
                int which=0, count=0;
                for(Map.Entry<Integer, Integer> entry: freq.entrySet()) {
                    if(entry.getValue()>count){
                        which = entry.getKey();
                        count = entry.getValue();
                    }
                }
                key.append((char)(' ' ^ which));
                if(time == 0) i = 1;
                else if(time == 1) i = 2;
                else break;
                time++;
                freq.clear();
            }
            int t = ascii.get(i);
            if (!freq.containsKey(t)) freq.put(t, 1);
            else freq.put(t, freq.get(t) + 1);
        }
        System.out.print(key);
        }
}

  • arora05saksham
     + 0 comments

    COOL AF!

    This question was actually very cool to solve. Mad fun!!

    Java Solution -

    I did it by

    Frequency analysis

    and by using

    XOR properties

    Complete brainstorming:

    I first thought I'd brute force the keys all over the search space and decrypt the whole text and would select the decrypted texts which would make sense and from that I will get the key. I thought I'd search the words 'and', 'or', 'the', 'if', 'so' etc. But this wasn't enough, it would not pass every test case; this approach was rather naive.

    It then clicked me,

    Why am I searching for common words when i can search for common letters!

    Because I recalled, the most occuring letter in english (only) is said to be e. Then every 'e' in the plaintext should've been converted to the same cipher character after XORing, right? That would mean the most occuring ascii character in the cipher text should be 'e' of the plain-text! for example, if the most occuring ascii character in the cipher text is, let's say '/' (slash) Then, because '/' occured the most, the XOR of '/' and KEY should give 'e'! ('/' ^ key = 'e') and from that, i can calculate the key, by using the property of XOR:

    key = '/' ^ 'e'

    BUT NO

    Because the encryption is done cyclicly by three characters in the key and not just 1 character. It then took me to the approach that I'd cyclicly divide the ciphertext into 3 separate ciphertexts and for every most occured character in each of these 3 ciphers, i'll one by one derive the key.

    IT STILL DID NOT WORK!

    That's because my assumptions and facts were wrong. The most occuring English Aplhabet is e but it's not true for complete texts. The most occuring character in probably every language is THE SPACE CHARACTER

    The ' ' character (ASCII 32!)

    So I finally changed my implementation from 'e' to ' ',

    AND IT WORKED!

    Here's the code in Java :)

    import java.util.*;

public class Solution {

    public static void main(String[] args) {
        List<Integer> ascii = new ArrayList<>();
        
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=0; i<n; i++)
            ascii.add(sc.nextInt());
        sc.close();
        
        Map<Integer, Integer> freq = new HashMap<>();
        StringBuilder key = new StringBuilder();
        
        for(int i=0, time=0;; i+=3){
            if(i>=ascii.size()){
                int which=0, count=0;
                for(Map.Entry<Integer, Integer> entry: freq.entrySet()) {
                    if(entry.getValue()>count){
                        which = entry.getKey();
                        count = entry.getValue();
                    }
                }
                key.append((char)(' ' ^ which));
                if(time == 0) i = 1;
                else if(time == 1) i = 2;
                else break;
                time++;
                freq.clear();
            }
            int t = ascii.get(i);
            if (!freq.containsKey(t)) freq.put(t, 1);
            else freq.put(t, freq.get(t) + 1);
        }
        System.out.print(key);
    }
}

  • pikoPistol
     + 0 comments

    Imo this is compact and runs quick!

    from itertools import product
from string import ascii_lowercase, printable

m=int(input())
d=input().split()

for k in product(ascii_lowercase,repeat=3):
    for i in range(m):
        if chr(int(d[i])^ord(k[i%len(k)]))not in" ();:,.'?-"+printable[:63]:
            break
    else:
        print("".join(k))
        break

  • JAIDHEER007
     + 0 comments

    C++ Solution

    int CalcXOR(int &x, char &ch){
    int y=int(ch);
    return (x | y) & (~x | ~y);
}
bool Check(int x){
    if(isalnum(x)||(strchr(" (;:,.'?-!)",x)!=NULL))
        return true;
    else
        return false;
}

int main(){
    int n; cin>>n;
    int *enc_ascii=new int[n];

    for(int i=0;i<n;i++){ cin>>enc_ascii[i]; }

    char ch1='a',ch2='a',ch3='a';

    for(bool br_co=false;ch1<='z';ch1++){
        for(int i=0;i<n;i+=3){
            if(!Check(CalcXOR(enc_ascii[i],ch1))){ 
                br_co=false; break; 
            }
            else{ br_co=true; }
        }
        if(br_co){ break; }
    }

    for(bool br_co=false;ch2<='z';ch2++){
        for(int i=1;i<n;i+=3){
            if(!Check(CalcXOR(enc_ascii[i],ch2))){ 
                br_co=false; break; 
            }
            else{ br_co=true; }
        }
        if(br_co){ break; }
    }

    for(bool br_co=false;ch3<='z';ch3++){
        for(int i=2;i<n;i+=3){
            if(!Check(CalcXOR(enc_ascii[i],ch3))){ 
                br_co=false; break; 
            }
            else{ br_co=true; }
        }
        if(br_co){ break; }
    }

    cout<<ch1<<ch2<<ch3;
    return 0;
}

  • habla2019
     + 0 comments

    Code that passes here doesn't work for PE. Any suggestions?