0
\$\begingroup\$

I have written a program in C, which encrypts and decrypts a c-styled string (const char *) and print the result to stdout. It requires key (const char *) and it's hash is calculated using Polynomial Rolling Hash.

My program makes sure that the hash of key must be in-between 0...128, using statement like size_t hash = get_hash(key) % 128;. My code works well if I provide a good key, but if the key is bad (plain[i] ± hash < 0), then it exits saying could not encrypt.

I have implemented all suggestion I got from my previous questions (not related this one).

Here's my code: TRY GOOD_KEY | TRY BAD_KEY

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

// gets hash of a string using Polynomial Rolling Hash 
// https://en.wikipedia.org/wiki/Rolling_hash#Polynomial_rolling_hash
static size_t get_hash(const char *a)
{
    if (a && *a != 0)
    {
        size_t p = 53;
        size_t m = 1e9 + 9;
        long long power_of_p = 1;
        long long hash_val = 0;

        for (size_t i = 0; a[i] != '\0'; i++)
        {
            hash_val = (hash_val + (a[i] - 97 + 1) * power_of_p) % m;
            power_of_p = (power_of_p * p) % m;
        }
        return (hash_val % m + m) % m;
    }
    return (size_t)-1;
}

// encrypts `plain` using `key` and stores the output on heap allocated memory `out`
static bool encrypt(const char *plain, char **out, const char *key)
{
    if (!plain || !out || !key)
        return false;
    size_t hash = get_hash(key) % 128;
    size_t len = strlen(plain);
    bool add = true;

    *out = calloc(len + 1, sizeof(char));
    if (!(*out))
        return false;

    for (size_t i = 0; plain[i] != '\0'; i++)
    {
        if (add == true && plain[i] + hash > '\0')
        {
            (*out)[i] = plain[i] + hash;
            add = false;
        }
        else if (add == false && plain[i] - hash > '\0')// should not be less than zero
        {
            (*out)[i] = plain[i] - hash;
            add = true;
        }
        else
        {
            free(*out);
            return false;
        }
    }
    return true;
}

// decrypts `enc` using `key` and stores the output on heap allocated memory `out`
static bool decrypt(const char *enc, char **out, const char *key)
{
    if (!enc || !out || !key)
        return false;
    size_t hash = get_hash(key) % 128;
    size_t len = strlen(enc);

    bool add_inrv = true;

    *out = calloc(len + 1, sizeof(char));
    if (!(*out))
        return false;

    for (size_t i = 0; enc[i] != '\0'; i++)
    {
        if (add_inrv == true && enc[i] - hash > '\0')
        {
            (*out)[i] = enc[i] - hash;
            add_inrv = false;
        }
        else if (add_inrv == false && enc[i] + hash > '\0')
        {
            (*out)[i] = enc[i] + hash;
            add_inrv = true;
        }
        else
        {
            free(*out);
            return false;
        }
    }
    return true;
}

int main(int argc, char const **argv)
{
    if (argc < 3)
    {
        perror("not enough input\nUsage: <MESSAGE> <KEY>");
        return EXIT_FAILURE;
    }
    printf("Your text: `%s`\n", argv[1]);
    char *enc, *after_dnc;

    if(!encrypt(argv[1], &enc, argv[2])){
        perror("could not encrypt");
        return EXIT_FAILURE;
    }

    printf("Encrypted: `%s`\n", enc);

    if(!decrypt(enc, &after_dnc, argv[2])){
        perror("could not decrypt");
        return EXIT_FAILURE;
    }

    printf("Decrypted: `%s`\n", after_dnc);

    free(enc);
    free(after_dnc);
    return EXIT_SUCCESS;
}

For output please use online compiler given above. I'm using GCC v11.2.0 on Arch Linux x86_64 using C17 standard.

\$\endgroup\$
1
  • \$\begingroup\$ Please define a C standard. What sign do you expect chars to have, or -42 % 128? Are you comfortable with 0 == hash(key)? What type do you assume plain[i] ± hash to have? \$\endgroup\$
    – greybeard
    Mar 30 at 6:21

2 Answers 2

1
\$\begingroup\$

If in the following I keep mentioning problems I see, that doesn't mean there isn't good:

  • there are comments telling what each function is good for
    (but for main())
    even where most are static (Not to be used outside compilation unit - why?)
  • I find the code fairly readable:
    naming and code formatting are inconspicious
    (hm. _inrv?)
  • you strive for const correctness

In all functions but get_hash(), you don't nest if (<can proceed>)s, but use early out. (I'd rather use 'a' than 97)

encrypt() seems to be to alternately add and subtract hash:
use a signed type and keep adding & inverting instead of conditional execution.
encrypt() and decrypt() are basically the same function - let's give using a common implementation a try:

static bool
crypt(const char *message, char ** const pout, const char *const key, bool add);

// encrypts `plain` using `key` and stores the output on heap allocated memory `out`
bool encrypt(const char *plain, char **out, const char *key)
{
    return crypt(plain, out, key, true);
}

// decrypts `enc` using `key` and stores the output on heap allocated memory `out`
bool decrypt(const char *enc, char **out, const char *key)
{
    return crypt(enc, out, key, false);
}

#define MAGIC   (128-1-1)
// crypts `message` using `key` and stores the output on heap allocated memory `pout`
static bool
crypt(const char *message, char ** const pout, const char *const key, bool add)
{
    if (!message || !pout || !key)
        return false;

    size_t len = strlen(message);

    char *out = *pout = malloc(len + 1);
    if (NULL == out)
        return false;
    out[len] = '\0';
    if (0 == len)
        return true;
    long hash = 1 + (get_hash(key) % (long)MAGIC);
    if (!add)
        hash = -hash;

    for (int i = 0 ; i < len ; i++)
    {
        out[i] = message[i] + hash;
        hash = -hash;
    }
    return true;
}
\$\endgroup\$
2
  • \$\begingroup\$ _inrv stands for inverse \$\endgroup\$ Mar 30 at 8:01
  • \$\begingroup\$ (additive_inverse, add_inverse - OK; add_invr sort of. Positive about _inrv?) \$\endgroup\$
    – greybeard
    Mar 30 at 9:12
2
\$\begingroup\$

Avoid unsigned math mistakes

My code works well if I provide a good key, but if the key is bad (plain[i] ± hash < 0)

plain[i] ± hash < 0 is never true. This is an unsigned compare. An unsigned sum/difference is never less than 0.

hash is an unsigned type and so dominates the compare. Note that enc[i] may be negative. Better to force the math, somehow to not depend on wrap-around

Really correct??
enc[i] - hash > '\0'
// This is the same as 
enc[i] - hash != '\0'

I suspect OP wants something like below.

enc[i] + CHAR_MAX + 1 > hash + CHAR_MAX + 1

... or force signed compare:

plain[i] ± (long) hash < 0

I am still unclear what the enc[i] - hash > 0 is really doing in the comment-less section of code.

Reduce with a prime

size_t hash = get_hash(key) % 128; only uses the lower 7 bits of get_hash(key). If the hash function get_hash() is a good one, then that is OK. Yet using size_t hash = get_hash(key) % some_prime; can make a weak hash better.

Do not compare a bool against true

// if (add == true ...
if (add ...

Unclear comment/code

"... sure that the hash of key must be in-between 0...128, using statement like size_t hash = get_hash(key) % 128" is unclear. Using get_hash(key) % 128 makes a key of [0...127], not 0...128 - depending on what that means. Be more explicit on the edge values to avoid off-by-one errors.

Size by the referenced object, not type

To know if sizeof(char) is correct, it obliges a review of the declaration, wherever it may be.

// Avoid
*out = calloc(len + 1, sizeof(char));

Instead, size to the object. It is easier to code right, review and maintain.

// Better
*out = calloc(len + 1, sizeof **out); // or some variation.

Minor: avoid negations

Rather than

if (!(*out))

consider

if (*out == NULL)

Avoidable use of ! tends to obfuscate.

Only for the pedantic

With rare (soon to be obsolete) non-2's complement, plain[i] != '\0' is a problem when char is signed (I wonder if such an animal exist today) as that stops the iteration on -0, when it should not.

A fix for that, and to avoid mixed sign-ness math, is to access strings via unsigned char*.

\$\endgroup\$
1
  • \$\begingroup\$ I am still unclear what the enc[i] - hash > 0 is really doing in the comment-less section of code. --- It was making sure that any character of encrypted and decrypted text doesn't contain '\0'. \$\endgroup\$ Mar 30 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.