Пользовательские класса Integer для расчета криптографических алгоритмов


Как я могу улучшить это целое-класс, который я написал? Я буду использовать это для вычисления интенсивных алгоритмов шифрования, в основном POLY1305AES. Я мог бы даже написать RSA с помощью этого. Я знаю, что существуют более эффективные алгоритмы, по крайней мере алгебраических операторов, но я буду переписывать тех, когда я узнаю их.

Прямо сейчас, я пытаюсь найти то, что я, возможно, пропустили во время написания этой.

  1. Должен ли я изменить мой контейнер?
  2. Может любой из алгоритмов можно улучшить?
  3. Что-то слишком много раз?
  4. Что я должен делать динамически?

Обратите внимание, что этот код может не работать, если ваш компилятор является слишком строгой, как ideone.com'ы компилятора (ошибки не вызваны отсутствием основных(); скорее, она думает, что некоторые операторы неоднозначно).

Есть много операторов, и мне все еще не хватает многих из них.

/*
integer.h
An integer type that does not have bit size restrictions
by Jason Lee @ calccrypto at yahoo dot com

NOTE: whether or not negative numbers will be implemented
      is yet to be determined
*/

#ifndef INTEGER_H
#define INTEGER_H

#include <cstdlib>
#include <deque>
#include <iostream>
#include <stdint.h>

// Checks platform bitsize using stdint.h
#ifndef BITS
    #define BITS 32
    #if INTPTR_MAX == INT64_MAX
        #undef BITS
        #define BITS 64
    #endif
#endif
// //////////////////////////////////////

class integer{
    private:
        void clean(){
            while ((value.begin() != value.end()) & !value.front())
                value.pop_front();
        }

        integer twos_complement(){
            return (~*this) + 1;
        }

    public:
        std::deque <uint8_t> value;
        // Constructors
        integer(){
            value.clear();
        }

        template <typename T>
        integer(T rhs){
            *this = rhs;
        }

        integer(std::deque <uint8_t> val){
            value = val;
            clean();
        }

        integer(const integer & rhs){
            value = rhs.value;
        }

        //  RHS input args only

        // Assignment Operator
        template <typename T> integer operator=(T rhs){
            value.clear();
            while (rhs > 0){
                value.push_front(rhs & 255);
                rhs >>= 8;
            }
            return *this;
        }

        integer operator=(integer rhs){
            value = rhs.value;
            return *this;
        }

        // Typecast Operators
        operator bool(){
            return (bool) value.size();
        }

        operator char(){
            return (char) value.back();
        }

        operator int(){
            int out = 0, count = 0;
            std::deque <uint8_t>::iterator i = value.end();
            while ((*this > 0) & (count < (BITS >> 3))){
                out += *(i++);
                count++;
            }
            return out;
        }

        operator uint8_t(){
            return value.back();
        }

        operator uint16_t(){
            std::deque <uint8_t>::iterator i = value.end();
            uint16_t out = value.back();
            out += *--i;
            return out;
        }

        operator uint32_t(){
            int out = 0, count = 0;
            std::deque <uint8_t>::iterator i = value.end();
            while ((*this > 0) && (count < 4))
                out += *(i++);
            return out;
        }

        operator uint64_t(){
            int out = 0, count = 0;
            std::deque <uint8_t>::iterator i = value.end();
            while ((*this > 0) && (count < 8))
                out += *(i++);
            return out;
        }

        // Bitwise Operators
        template <typename T> integer operator&(T rhs){
            return *this & integer(rhs);
        }

        integer operator&(integer rhs){
            std::deque <uint8_t> larger = value, smaller = rhs.value;
            if (value.size() < rhs.value.size())
                larger.swap(smaller);
            for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)
                *i &= *j;
            return integer(smaller);
        }

        template <typename T> integer operator|(T rhs){
            return *this | integer(rhs);
        }

        integer operator|(integer rhs){
            std::deque <uint8_t> larger = value, smaller = rhs.value;
            if (value.size() < rhs.value.size())
                larger.swap(smaller);
            while (smaller.size() < larger.size())
                smaller.push_front(0);
            for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)
                *j |= *i;
            return integer(larger);
        }

        template <typename T> integer operator^(T rhs){
            return *this ^ integer(rhs);
        }

        integer operator^(integer rhs){
            std::deque <uint8_t> larger = value, smaller = rhs.value;
            if (value.size() < rhs.value.size())
                larger.swap(smaller);
            while (smaller.size() < larger.size())
                smaller.push_front(0);
            for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)
                *j ^= *i;
            return integer(larger);
        }

        template <typename T> integer operator&=(T rhs){
            *this = *this & rhs;
            return *this;
        }

        integer operator&=(integer rhs){
            *this = *this & rhs;
            return *this;
        }

        template <typename T> integer operator|=(T rhs){
            *this = *this | rhs;
            return *this;
        }

        integer operator|=(integer rhs){
            *this = *this | rhs;
            return *this;
        }

        template <typename T> integer operator^=(T rhs){
            *this = *this ^ rhs;
            return *this;
        }

        integer operator^=(const integer rhs){
            *this = *this ^ rhs;
            return *this;
        }

        integer operator~(){
            std::deque <uint8_t> out = value;
            std::deque <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
            j--;
            for(i = i; i != j; i++)
                *i ^= 0xff;
            // get highest bit
            int8_t top = 8;
            while (!((1 << top) & *i))
                top--;
            for(top = top; top > -1; top--)
                *i ^= 1 << top;
            return integer(out);
        }

        // Bit Shift Operators
        integer operator<<(unsigned int shift){
            if (*this == 0)
                return *this;
            std::deque <uint8_t> out = value;
            for(unsigned int i = 0; i < (shift >> 3); i++)
                out.push_back(0);
            shift &= 7;
            if (shift){
                out.push_front(0);
                std::deque <uint8_t>::iterator i = out.begin(), j = out.end();
                i++; j--;
                for(; i != j; i++){
                    uint8_t temp = *i >> (8 - shift);
                    --i;
                    *i += temp;
                    i++;
                    *i = (uint8_t) (*i << shift);
                }
                uint8_t temp = *i >> (8 - shift);
                i--;
                *i += temp;
                i++;
                *i <<= shift;
            }
            return integer(out);
        }

        integer operator<<(integer shift){
            integer out = *this;
            for(integer i = 0; i < (shift >> 3); i++)
               out <<= 8;
            for(integer i = 0; i < (shift & 7); i++)
                out <<= 1;
            return out;
        }

        integer operator>>(unsigned int shift){
            if (shift >= bits())
                return integer(0);
            std::deque <uint8_t> out = value;
            for(unsigned int i = 0; i < (shift >> 3); i++)
                out.pop_back();
            shift &= 7;
            if (shift){
                std::deque <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
                j--;
                for(; i != j; i++){
                    *i >>= shift;
                    i++;
                    uint8_t temp = *i << (8 - shift);
                    i--;
                    *i += temp;
                }
                *j >>= shift;
            }
            return integer(out);
        }

        integer operator>>(integer shift){
            integer out = *this;
            for(integer i = 0; i < (shift >> 3); i++)
               out >>= 8;
            for(integer i = 0; i < (shift & 7); i++)
                out >>= 1;
            return out;
        }

        integer operator<<=(size_t shift){
            *this = *this << shift;
            return *this;
        }

        integer operator>>=(size_t shift){
            *this = *this >> shift;
            return *this;
        }

        integer operator<<=(integer shift){
            *this = *this << shift;
            return *this;
        }

        integer operator>>=(integer  shift){
            *this = *this >> shift;
            return *this;
        }

        // Logical Operators
        bool operator!(){
            return !(bool) *this;
        }

        template <typename T> bool operator&&(T rhs){
            return (bool) (*this && rhs);
        }

        template <typename T> bool operator&&(integer rhs){
            return (bool) *this && (bool) rhs;
        }

        template <typename T> bool operator||(T rhs){
            return ((bool) *this) || rhs;
        }

        template <typename T> bool operator||(integer rhs){
            return ((bool) *this) || (bool) rhs;
        }

        // Comparison Operators
        template <typename T> bool operator==(T rhs){
            return (value == integer(rhs).value);
        }

        bool operator==(integer rhs){
            return (value == rhs.value);
        }

        template <typename T> bool operator!=(T rhs){
            return !(*this == rhs);
        }

        bool operator!=(integer rhs){
            return !(*this == rhs);
        }

        template <typename T> bool operator>(T rhs){
            return (*this > integer(rhs));
        }

        bool operator>(integer rhs){
            if (bits() > rhs.bits())
                return true;
            if (bits() < rhs.bits())
                return false;
            if (value == rhs.value)
                return false;
            for(unsigned int i = 0; i < value.size(); i++)
                if (value[i] != rhs.value[i])
                    return value[i] > rhs.value[i];
            return false;
        }

        template <typename T> bool operator<(T rhs){
            return (*this < integer(rhs));
        }

        bool operator<(integer rhs){
            if (bits() < rhs.bits())
                return true;
            if (bits() > rhs.bits())
                return false;
            if (value == rhs.value)
                return false;
            for(unsigned int i = 0; i < value.size(); i++)
                if (value[i] != rhs.value[i])
                    return value[i] < rhs.value[i];
            return false;
        }

        template <typename T> bool operator>=(T rhs){
            return ((*this > rhs) | (*this == rhs));
        }

        bool operator>=(integer rhs){
            return ((*this > rhs) | (*this == rhs));
        }

        template <typename T> bool operator<=(T rhs){
            return ((*this < rhs) | (*this == rhs));
        }

        bool operator<=(integer rhs){
            return ((*this < rhs) | (*this == rhs));
        }

        // Arithmetic Operators
        template <typename T> integer operator+(T rhs){
            return *this + integer(rhs);
        }

        integer operator+(integer rhs){
            if (rhs == 0)
                return *this;
            if (*this == 0)
                return rhs;
            std::deque <uint8_t> top = value, bottom = rhs.value;
            if (value.size() < rhs.value.size())
                top.swap(bottom);
            top.push_front(0);
            while (bottom.size() + 1 < top.size())
                bottom.push_front(0);
            bool carry = false, next_carry;
            for(std::deque <uint8_t>::reverse_iterator i = top.rbegin(), j = bottom.rbegin(); j != bottom.rend(); i++, j++){
                next_carry = ((*i + *j + carry) > 255);
                *i += *j + carry;
                carry = next_carry;
            }
            if (carry)
                *top.begin() = 1;
            return integer(top);
        }

        template <typename T> integer operator+=(T rhs){
            *this = *this + rhs;
            return *this;
        }

        integer operator+=(integer rhs){
            *this = *this + rhs;
            return *this;
        }

        template <typename T> integer  operator-(T rhs){
            return *this - integer(rhs);
        }

        integer operator-(integer rhs){
            if (rhs == 0)
                return *this;
            if (*this == rhs)
                return integer(0);
            if (rhs > *this)
                exit(2);// to be worked on
            unsigned int old_b = rhs.bits();
            rhs = rhs.twos_complement();
            for(unsigned int i = old_b; i < bits(); i++)
                rhs ^= integer(1) << i;
            return (*this + rhs) & (~(integer(1) << bits()));   // Flip bits to get max of 1 << x
        }

        template <typename T> integer operator-=(T rhs){
            *this = *this - rhs;
            return *this;
        }

        integer operator-=(integer rhs){
            *this = *this - rhs;
            return *this;
        }

        template <typename T> integer operator*(T rhs){
            return *this * integer(rhs);
        }

        integer operator*(integer rhs){
            // long multiplication
            unsigned int zeros = 0;
            std::deque <uint8_t> row;
            std::deque <std::deque <uint8_t> > temp;
            integer out = 0;
            for(std::deque <uint8_t>::reverse_iterator i = value.rbegin(); i != value.rend(); i++){
                row = std::deque <uint8_t>(zeros++, 0); // zeros on the right hand side
                uint8_t carry = 0;
                for(std::deque <uint8_t>::reverse_iterator j = rhs.value.rbegin(); j != rhs.value.rend(); j++){
                    uint16_t prod = (uint16_t(*i) * uint16_t(*j)) + carry;// multiply through
                    row.push_front((uint8_t) prod);
                    carry = prod >> 8;
                }
                if (carry != 0)
                    row.push_front(carry);
                out += integer(row);
            }
            return out;
        }

        template <typename T> integer operator*=(T rhs){
            *this = *this * integer(rhs);
            return *this;
        }

        integer operator*=(integer rhs){
            *this = *this * rhs;
            return *this;
        }

        template <typename T> integer operator/(T rhs){
            return *this / integer(rhs);
        }

        integer operator/(integer rhs){
            if (rhs == 0){
                std::cout << "Error: division or modulus by zero" << std::endl;
                exit(1);
            }
            if (rhs == 1)
                return *this;
            if (*this == rhs)
                return integer(1);
            if ((*this == 0) | (*this < rhs))
                return integer(0);
            // Checks for divisors that are powers of two
            uint16_t s = 0;
            integer copyd(rhs);
            while ((copyd & 1) == 0){
                copyd >>= 1;
                s++;
            }
            if (copyd == 1)
                return *this >> s;
            ////////////////////////////////////////////////
            integer copyn(*this), quotient = 0;
            while (copyn >= rhs){
                copyd = rhs;
                integer temp(1);
                while ((copyn >> 1) > copyd){
                    copyd <<= 1;
                    temp <<= 1;
                }
                copyn -= copyd;
                quotient += temp;
            }
            return quotient;
        }

        template <typename T> integer operator/=(T rhs){
            *this = *this / integer(rhs);
            return *this;
        }

        integer operator/=(integer rhs){
            *this = *this / rhs;
            return *this;
        }

        template <typename T> integer operator%(T rhs){
            return *this - (integer(rhs) * (*this / integer(rhs)));
        }

        integer operator%(integer rhs){
            *this = *this - (*this / rhs) * rhs;
            return *this;
        }

        template <typename T> integer operator%=(T rhs){
            *this = *this % integer(rhs);
            return *this;
        }

        integer operator%=(integer rhs){
            *this = *this % rhs;
            return *this;
        }

        // Increment Operator
        integer operator++(){
            *this += 1;
            return *this;
        }

        integer operator++(int){
            integer temp(*this);
            ++*this;
            return temp;
        }

        // Decrement Operator
        integer operator--(){
            *this -= 1;
            return *this;
        }

        integer operator--(int){
            integer temp(*this);
            --*this;
            return temp;
        }

        // get private value
        unsigned int bits(){
            if (value.empty())
                return 0;
            unsigned int out = value.size() << 3;
            uint8_t top = 128;
            while (!(value.front() & top)){
                out--;
                top >>= 1;
            }
            return out;
        }

        std::deque <uint8_t> data(){
            return value;
        }
};
// lhs type T as first arguemnt

// Bitwise Operators
template <typename T> T operator&(T lhs, integer rhs){
    return (T) (rhs & lhs);
}

template <typename T> T operator|(T lhs, integer rhs){
    return (T) (rhs | lhs);
}

template <typename T> T operator^(T lhs, integer rhs){
    return (T) (lhs * rhs);
}

template <typename T> T operator&=(T & lhs, integer rhs){
    lhs = (T) (integer(lhs) & rhs);
    return lhs;
}

template <typename T> T operator|=(T & lhs, integer rhs){
    lhs = (T) (integer(lhs) | rhs);
    return lhs;
}

template <typename T> T operator^=(T & lhs, integer rhs){
    lhs = (T) (integer(lhs) ^ rhs);
    return lhs;
}

// Comparison Operators
template <typename T> bool operator==(T lhs, integer rhs){
    return (rhs == lhs);
}

template <typename T> bool operator!=(T lhs, integer rhs){
    return (rhs != lhs);
}

template <typename T> bool operator>(T lhs, integer rhs){
    return (rhs < lhs);
}

template <typename T> bool operator<(T lhs, integer rhs){
    return (rhs > lhs);
}

template <typename T> bool operator>=(T lhs, integer rhs){
    return (rhs <= lhs);
}

template <typename T> bool operator<=(T lhs, integer rhs){
    return (rhs >= lhs);
}

// Arithmetic Operators
template <typename T> T operator+(T lhs, integer rhs){
    return (T) (rhs + lhs);
}

template <typename T> T & operator+=(T & lhs, integer rhs){
    lhs = lhs + rhs;
    return lhs;
}

template <typename T> T operator-(T lhs, integer rhs){
    return (T) (integer(rhs) - lhs);
}

template <typename T> T & operator-=(T & lhs, integer rhs){
    lhs = lhs - rhs;
    return lhs;
}

template <typename T> T operator*(T lhs, integer rhs){
    return (T) (rhs * lhs);
}

template <typename T> T & operator*=(T & lhs, integer rhs){
    lhs = (T) (rhs * lhs);
    return lhs;
}

template <typename T> T operator/(T lhs, integer rhs){
    return (T) (integer(lhs) / rhs);
}

template <typename T> T & operator/=(T & lhs, integer rhs){
    lhs = lhs / rhs;
    return lhs;
}
template <typename T> T operator%(T lhs, integer rhs){
    return (T) (integer(lhs) % rhs);
}

template <typename T> T & operator%=(T & lhs, integer rhs){

    lhs = lhs % rhs;
    return lhs;
}

// IO Operator
std::ostream & operator<<(std::ostream & stream, integer rhs){
    std::string out = "";
    if (rhs == 0)
        out = "0";
    else {
        int div = 10;
        if (stream.flags() & stream.oct)
            div = 8;
        if (stream.flags() & stream.dec)
            div = 10;
        if (stream.flags() & stream.hex)
            div = 16;
        while (rhs > 0){
            out = "0123456789abcdef"[(rhs % div).data().back()] + out;
            rhs /= div;
        }
    }
    stream << out;
    return stream;
}

#endif // INTEGER_H


2142
7
задан 30 июня 2011 в 02:06 Источник Поделиться
Комментарии
2 ответа

#define BITS 32
#if INTPTR_MAX == INT64_MAX
#undef BITS
#define BITS 64
#endif

#определить это, и при необходимости #фдоонИнг это некрасиво. Использование другого блока с параллельными #определитьс вместо.

    integer(){
value.clear();
}

значение будет пустым, когда объект строится, поэтому нет необходимости, чтобы очистить его.

    operator char(){
return (char) value.back();
}

Преобразование в тип char , игнорируя все, кроме одного элемента, как мне кажется, опрометчиво.

   operator uint64_t(){
int out = 0, count = 0;
std::deque <uint8_t>::iterator i = value.end();
while ((*this > 0) && (count < 8))
out += *(i++);
return out;
}

Вам действительно нужно преобразовать в так много различных целочисленных типов? Вы должны, вероятно, утверждать/выводит сообщение об ошибке, если значение не может быть сохранено в формате, типа.

    integer operator|(integer rhs){
std::deque <uint8_t> larger = value, smaller = rhs.value;

Вы делаете ненужные копии данных здесь.

        if (value.size() < rhs.value.size())
larger.swap(smaller);
while (smaller.size() < larger.size())
smaller.push_front(0);
for(std::deque <uint8_t>::reverse_iterator i = smaller.rbegin(), j = larger.rbegin(); i != smaller.rend(); i++, j++)

Почему вы используете обратный итератор?

            *j |= *i;
return integer(larger);
}

В & оператор очень похож; они должны быть переработаны, чтобы исключить дублирование кода.

    integer operator~(){
std::deque <uint8_t> out = value;
std::deque <uint8_t>::reverse_iterator i = out.rbegin(), j = out.rend();
j--;

я и Джей не очень полезны имена.

        for(i = i; i != j; i++)
*i ^= 0xff;
// get highest bit
int8_t top = 8;
while (!((1 << top) & *i))
top--;
for(top = top; top > -1; top--)
*i ^= 1 << top;
return integer(out);
}

Вы не можете просто применить ~ для всех элементов? Во всяком случае, некоторые комментарии, почему вы делаете то, что вы делаете здесь, будет полезно.

10
ответ дан 1 июля 2011 в 08:07 Источник Поделиться

Для Здесь:

while ((value.begin() != value.end()) & !value.front())

Вы должны использовать логическое && вместо &.

7
ответ дан 1 июля 2011 в 03:07 Источник Поделиться