Linear cryptanalysis of a substitution permutation network

I was translating a script I had that would automate linear cryptanalysis of SP networks from Python to C++. For those who aren't familiar with cryptography, linear cryptanalysis involves finding relationships between certain input and output bits of a \$1 \rightarrow 1\$ array.

What I'm doing is looping over all possible input bits and output bits, then seeing how many times there's a correlation between the bits. If this correlation is above a threshold value, I store it and move on.

My main problem is that running the substitute_rounds(rounds) function after rounds = setup_first_round() takes nearby 5 times as long to ran than the Python version did! Clearly, I wrote substitute_rounds() poorly!

Any suggestions would be very helpful, but I'm primarily trying to get a speed boost on substitute_rounds().

Two functions (Cartesian product and combinations) were just copy pasted from Stack Overflow, so I'm showing them after my code.

```
#include
#include
#include
#include "math.h"

#define bits_in_sbox 8
#define subkey_bits 64
#define default_threshold 0.0625

using namespace std;

//return the i'th bit of s
inline bool ith_bit(int s, short i)
{
return (s >> i) & 1;
}

//I use shorts instead of ints here because of memory issues
//with each new round, the # of these I have to store goes up exponentially
struct linear_relationship
{
std::vector inputs;
std::vector outputs;
float bias;
};

//only used for debugging
void print_linear_relationship(linear_relationship & i)
{
for(auto &j:i.inputs)std::cout bit(std::vector & inputs, short * sbox)
{
std::vector ret;

//offset for shifting the output bits
int offset = inputs[0] - (inputs[0] % bits_in_sbox);

//make the inputs directly enterable as indexes of the sbox
//so bit 8 -> bit 0, bit 25 -> bit 1
std::vector normalized_inputs;
for(short i: inputs)
normalized_inputs.push_back(i % bits_in_sbox);

std::vector output_bits_index;
for(short i =

Try this version. I've made only two changes:

-
Pass function parameters by const reference, rather than by (modifiable) reference, if you're promising not to modify them.

-
In ranged for loops, always use for (auto&& elt : container) unless you know exactly what you're doing. Using bare auto means "make a copy of the element", which is the cause of a lot of your slowness: you're making copies of some pretty big vectors, if I understand correctly.

std::vector substitute_rounds(
    const std::vector& rounds,
    const short **sboxes)
{
    std::vector ret;

    for (auto&& line: rounds) {
        std::vector> grouped_inputs = group_inputs(line);
        Vvi next_round_linearity;

        for (auto&& i : grouped_inputs) {
            // picks the sbox to use based on the index of the grouped subsection of the input bits
            const short *sbox = sboxes[i[0] / bits_in_sbox];
            next_round_linearity.push_back(bit(i, sbox));
        }

        Vvi output;
        cart_product(output, next_round_linearity);

        for (auto&& i : output) {
            ret.push_back(merge_linear_relationships(i, line));
        }
    }

    return ret;
}

For more on auto&& and what it means exactly (and why it's the proper default when you don't care about the details), see Stephan T. Lavavej's N3994 "Ranged For Loops: The Next Generation". Basically, it'll make a reference with the proper degree of constness and rvalueness for whatever the thing is that you're trying to iterate over.

auto& or const auto& would also work in this case, but not necessarily in all cases. The big thing in this case is to stay away from reference-less auto, because that makes copies.

StackExchange Code Review Q#94851, answer score: 2