How easy is it to crack this encryption algorithm?

Question

When I was about 13 or 14 years old, I was a little interested in cryptography (which is, after all, an interesting field). I learnt quite a lot since that time (it has been about 8 years since then), but I'm still very far away from considering myself an expert in cryptography.

Whatever, when I was at that age, I wrote this little Perl script which I just found on an old HD. (Saved as MyEncrypt.pm)

package MyEncrypt;

use strict;
use warnings;

my @_ALPHABET = ('a' .. 'z', 'A' .. 'Z', 0 .. 10, ' ');
my $_i = 0;
my %_ALPHABET = map { $_i++; $_ => $_i } @_ALPHABET;
$_i = 0;
my %_ALPHABET_REVERSE = map { $_i++; $_i => $_ } @_ALPHABET;

sub new {
    bless +{}, shift
}

sub set_password {
    my $self = shift;
    my $password = shift;
    $self->{hashed_password} = _hash_password($password);
    return $self;
}

sub encrypt {
    my $self = shift;
    my $input = shift;

    my $hashed_password = $self->{hashed_password};
    die "No password set.\n" unless $hashed_password;

    my @split = split(//, $input);

    my $output = shift;
    for (0 .. $#split) {
        my $new_number .= ($_ALPHABET{$split[$_]} + ($hashed_password ** ($_ + 1))) % $#_ALPHABET;
        $output .= $_ALPHABET_REVERSE{$new_number};
    }
    return $output;
}

sub _hash_password {
    my $password = shift;
    my $hash = 1;
    my $i = 1;
    for (split(//, $password)) {
        my $power = length($password) / (2 ** $i);
        $power = 1 if $power < 1;
        $hash *= int($_ALPHABET{$_} ** $power);
        $i++;
    }

    if(is_multiple_of_two($hash)) {
        $hash += 1;
    }

    while (length($hash) != 10) {
        no warnings;
        $hash *= $hash | join('', map { $_ALPHABET{$_} } split(//, $password));
        $hash =~ s/\.//g;
        $hash = substr($hash, 0, 10);
    }
    return $hash;
}

sub is_multiple_of_two {
    my $n = shift;
    my $log = log($n) / log(2);
    if($log == int($log)) {
        return 1;
    } else {
        return 0;
    }
}

1;

(It probably has the worst hashing-algorithm ever. I know).

This is my "test-program" for it:

use strict;
use warnings;
use MyEncrypt;

my $enc = MyEncrypt->new();
$enc->set_password('abc');
die $enc->encrypt("hello world");

My idea was this: We give it a password and it somehow generates a "hash" of it (here in a way that, I admit, I don't quite understand anymore. For some reason, it should be 10 digits long and these are generated by, until the password is 10 digits long, multiplying the password with the OR'd characters of the alphabet (where a = 1, ... A = 27, ...) and then cutting it to 10 characters or less, until this leads to a "hash"), which is then later used for this letter-by-letter-substitution:

x = (number of the actual letter + password_hash to the power of (position of this character + 1)) modulo the size of the alphabet

and then x is used to look for the letter numbered x, which will be added to the output-string. When gone through all the text, the output will have a completely different form of what it had as input. And when one letter changes in the password, the whole string is different.

E.g.:

string: "hello world", pass: "abc" => 9bkpXY1H0oR
string: "hello world", pass: "abcd" => HS4gVkuWX4U
string: "hello world", pass: "abcda" => DhAqIeHn9cr

and so on.

Of course, the code is terrible, the hashing-algorithm is probably the worst one ever and the idea is not really new, but I came up with it myself and at that time I was quite proud of myself for this. But how secure would this have been? How much time would one need to decrypt this and how would this be done? As I've said, I developed in many fields, but for some reason after that script I did not care so much about cryptography anymore and my knowledge there is quite limited.

Answer 1

Your encryption scheme basically takes a string and does a one-to-one mapping of characters to 63 numbers (0 to 62). Ignoring this straightforward mapping of characters, your scheme basically is the i-th character of the ciphertext (1-indexed) is c[i] = (p[i] + H**i) % N, where N is the size of the alphabet (63), p[i] is i-th character of the plaintext, and H is the hash calculated from the password.

Decryption should be straightforward as p[i] = (c[i] - H**i) % N.

But the code doesn't work -- decryption is impossible

First, the code is seriously flawed as perl handles integer overflow by switching to floating point numbers rather than moving to a big integer library.

For example, for pw="abc" the hash is 8486571168 (as seen by inserting a print statement). Note for say the second character in the array you calculate 8486571168**2 in perl is 7.20218901895289e+19 -- an double precision floating point number. Note adding any number 0 to 63 to 7.20218901895289e+19 leaves the value unchanged in a double -- hence your code doesn't work -- it loses the original value of the plaintext due to rounding errors from using floating point math.

You can easily demonstrate this by using the same password (abc) to encrypt say "hBROKEN1234" or "hNOTWORKING" (or anything else starting with an h of this length). Regardless of the plaintext, the generated "ciphertext" will always be "9bkpXY1H0oR". You could fix this by using modular exponentiation library or a big-integer math library, or switching to a language like python that has big integer math built-in. Note, it suffices to show that an encryption method is broken if the same key encrypts two different plaintexts to the exact same ciphertext. If that happens clearly there is no decryption function, as the decryption function takes the key and the ciphertext and needs to recover the original plaintext.

Furthermore the algorithm is trivially attackable

Second, this scheme if fixed would be trivial to attack. You merely have to try to decrypt with all N (length of your alphabet) different values of the hash (modulo the alphabet size) and at least one of them should work.

If you understand modular arithmetic (if not see below) you will see your encryption method for each character c[i] = (p[i] + H**i) % N is exactly equivalent to c[i] = p[i] + (H % N)**i) % N. This is bad as there are only N possible values of H % N (and in our case N=63), so its trivial to try decrypting with H=0 to H=62 until you find something that is meaningful data.

Background on modular arithmetic

To see this note we are doing modular arithmetic. In modular arithmetic, there's the concept of congruent numbers; e.g., on a clock face (modulo 12) there's no difference between 3 o'clock or 15 o'clock, or 51 o'clock (48+3), so we say \$3 \equiv 15 \equiv 51 \;(\bmod 12)\$ -- the notation is to only write \$(\bmod N)\$ in parenthesis at the end, even though it applies to the whole equation (all sides).

When you do modular arithmetic for the most part, it doesn't matter if you take the modulus step early. This is easy to see for addition. if you add 7 hours to 3 o'clock, you get 10. Similarly if you add 31 hours (\$31 = 7 \bmod 12\$) to 15 o'clock, you again get 10 on the clock face. To formalize this notation, let's define two pairs of congruent numbers modulo N, specifically \$a \equiv A\;(\bmod N)\$ which means \$A = a + m N\$ for some integer \$m\$ (\$m\$ could be positive, negative or zero), and similarly let \$b \equiv B \;(\bmod N)\$ and \$B = b + n N\$ for some integer \$n\$. Doing the addition we get \$A + B = a + b + (m + n) N\$, and since \$m + n\$ is also an integer we just showed the \$A + B \equiv a + b\; (\bmod N)\$. You can do similar proofs for subtraction, multiplication, and exponentiation. works. The proof for multiplication: $$\begin{eqnarray} A B &=& (a + m N)(b + n N)\\ &=& a b + m b N + n a N + m n N N \\ &=& a b + (m b + n a + m n N) N \\ \therefore A B &\equiv& a b\; (\bmod N) \end{eqnarray}$$

Similarly for the base in exponentiation, we can show we can take the modulus (of the base) can be done early as

$$\begin{eqnarray} A^k &=& (a + m N)^k\\ &=& \sum_{i=0}^k {k \choose i}a^{k-i} (m N)^i \\ &=& a^k + \sum_{i=1}^k {k \choose i}a^{k-i} m^i N^i \\ &=& a^k + N \left(\sum_{i=1}^k {k \choose i}a^{k-i} m^i N^{i-1} \right) \\ \therefore A^k &\equiv& a^k\; (\bmod N) \end{eqnarray}$$

where the binomial theorem was used. Thus we are allowed to take an expression like (a + b**x) % N and change it to (a + (b % N)**x) % N and it won't change the result and thus only need to try all the values of (h % N) when brute-force decrypting.

Answer 2

Just some quick thoughts (I can't even read Perl nor do I know much about crypto).

1. The last module could lead to problems in decrypting. I understand that you want your cypter text be easily viewable but what if your $new_number before the module happend to be bigger len(alphabet)? How would the decryptor know which of the infinte multiplies it was
2. Why don't you want odd hashes? Just adding one makes hash-collision twice as likely
3. Assuming that you have a static key and the attacker can force the encryption of text of his choosing - what happens if AAAAAAAAAAAAAAA is encrypted? As each letter is the same finding out the hash of the key can be done by analyzing the cypertext

And did you even write a decryption function to test whether your ecryption is any useful?