From: Ummon Date: Mon, 15 Dec 2014 12:35:31 +0000 (+0100) Subject: First commit. X-Git-Url: http://git.euphorik.ch/?p=crypto_lab3.git;a=commitdiff_plain;h=7975d02c6c1ee679a236087e86955c086f1a9a8e First commit. --- 7975d02c6c1ee679a236087e86955c086f1a9a8e diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..bc14d9e --- /dev/null +++ b/.gitignore @@ -0,0 +1,27 @@ +lab3-build/ +*.aux +*.log +*.[oa] +moc_*.cpp +*.moc +*.pb.cc +*.pb.h +*.pb.cpp +*.user +*.user.* +*.session +*.Release +*.Debug +*.exe +*.qm +*.dll +Makefile* +output/ +Installations/ +.tmp/ +/doc/doxygen/html +qrc_*.cpp +TODO +*.session +*.DS_STORE +Thumbs.db diff --git a/icr14_lab_03.pdf b/icr14_lab_03.pdf new file mode 100644 index 0000000..5dd5a2a Binary files /dev/null and b/icr14_lab_03.pdf differ diff --git a/rapport/main.tex b/rapport/main.tex new file mode 100644 index 0000000..19a579f --- /dev/null +++ b/rapport/main.tex @@ -0,0 +1,40 @@ +\documentclass[a4paper,10pt]{article} + +\usepackage[francais]{babel} +\usepackage[utf8]{inputenc} +\usepackage[T1]{fontenc} +\usepackage{lmodern} + +\usepackage{graphicx} +\usepackage{listings} +\usepackage{url} +\usepackage{upquote} +\usepackage{color} +\usepackage[usenames,dvipsnames]{xcolor} + +\title{ICR - Labo \#3 : \textit{Attaque par faute contre RSA-CRT}} +\author{G.Burri} + + +\begin{document} + +\nocite{*} + +\maketitle + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\section{Introduction} + + + + + +%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% +\section{Conclusion} + + +%\bibliographystyle{plain} +%\bibliography{main} + +\end{document} diff --git a/src/Rand.cpp b/src/Rand.cpp new file mode 100644 index 0000000..c82b83f --- /dev/null +++ b/src/Rand.cpp @@ -0,0 +1,65 @@ +#include "Rand.h" + +#include +#include +#include +using namespace std; + +mpz_class Rand::randSize(int sizeBits, bool forceSize) +{ + const int nbBitsFirstByte = ((sizeBits - 1) % 8) + 1; // >= 1 and <= 8 + const int nbBytes = sizeBits / 8 + (nbBitsFirstByte != 8 ? 1 : 0); + + // A fixed rand value used during benchmark tests. + // char randBytes[] {(char)0x3d, (char)0x3f, (char)0x74, (char)0xa3, (char)0xcb, (char)0xba, (char)0x2e, (char)0x26, (char)0xf4, (char)0x5a, (char)0x05, (char)0xb0, (char)0x91, (char)0x2d, (char)0x13, (char)0x4c, (char)0x81, (char)0xa4, (char)0x4e, (char)0x8d, (char)0x50, (char)0xc6, (char)0xa5, (char)0x6e, (char)0x69, (char)0x3b, (char)0x1d, (char)0xa1, (char)0x68, (char)0x79, (char)0x87, (char)0xbe, (char)0xbf, (char)0xc0, (char)0x3d, (char)0x06, (char)0x4a, (char)0x74, (char)0xc8, (char)0x36, (char)0xa0, (char)0x92, (char)0x0c, (char)0xb4, (char)0x99, (char)0x6e, (char)0x64, (char)0x27, (char)0x61, (char)0x18, (char)0xe5, (char)0x07, (char)0xf1, (char)0xcb, (char)0x45, (char)0x57, (char)0x84, (char)0xa8, (char)0xbc, (char)0x25, (char)0x00, (char)0x1c, (char)0x7f, (char)0x1c, (char)0xf7, (char)0x40, (char)0xc5, (char)0x09, (char)0x73, (char)0xbf, (char)0xde, (char)0xb2, (char)0x65, (char)0x15, (char)0x64, (char)0xb4, (char)0x94, (char)0x8f, (char)0x1c, (char)0x6b, (char)0x84, (char)0x4b, (char)0x69, (char)0x6f, (char)0xc7, (char)0x71, (char)0x26, (char)0x3c, (char)0x58, (char)0x5f, (char)0x08, (char)0x34, (char)0x29, (char)0x9a, (char)0xfb, (char)0x95, (char)0x9d, (char)0x4f, (char)0x27, (char)0x49, (char)0x94, (char)0xc4, (char)0x26, (char)0x76, (char)0xc1, (char)0x8e, (char)0x30, (char)0x7f, (char)0x93, (char)0x63, (char)0x68, (char)0x3c, (char)0x0b, (char)0x8f, (char)0x5d, (char)0xff, (char)0x09, (char)0x68, (char)0x1b, (char)0x41, (char)0xea, (char)0xfd, (char)0xe1, (char)0xd5, (char)0x77, (char)0x1d, (char)0x3b, (char)0xda, (char)0x6f, (char)0xb8, (char)0xbe, (char)0x86, (char)0x25, (char)0x8a, (char)0xc1, (char)0x2c, (char)0x87, (char)0xd0, (char)0x24, (char)0xe9, (char)0x0d, (char)0xb3, (char)0x23, (char)0xcb, (char)0x40, (char)0xa3, (char)0x40, (char)0xc7, (char)0x2c, (char)0x3e, (char)0x08, (char)0xdf, (char)0xdc, (char)0xaa, (char)0x7a, (char)0x4a, (char)0x02, (char)0x23, (char)0x73, (char)0xb3, (char)0xc9, (char)0xe5, (char)0x2a, (char)0x36, (char)0xf3, (char)0xd1, (char)0x59, (char)0xfd, (char)0x74, (char)0x63, (char)0x46, (char)0x92, (char)0x47, (char)0x48, (char)0xf0, (char)0x05, (char)0x4c, (char)0xf9, (char)0x92, (char)0xe2, (char)0xe8, (char)0x7e, (char)0x52, (char)0x1a, (char)0x84, (char)0x47, (char)0x9a, (char)0xb5, (char)0x25, (char)0xdc, (char)0xb2, (char)0xed, (char)0x02, (char)0x65, (char)0x76, (char)0x3e, (char)0xad, (char)0xc0, (char)0x3c, (char)0xa0, (char)0x30, (char)0x83, (char)0x0c, (char)0xbe, (char)0x09, (char)0x63, (char)0x36, (char)0x3c, (char)0xc4, (char)0x94, (char)0x79, (char)0x74, (char)0x30, (char)0x71, (char)0x1b, (char)0xac, (char)0x0c, (char)0x2f, (char)0xcf, (char)0xf4, (char)0x68, (char)0x26, (char)0xd9, (char)0xb4, (char)0xb5, (char)0x3c, (char)0x07, (char)0x41, (char)0xa4, (char)0xde, (char)0x80, (char)0x00, (char)0x70, (char)0x06, (char)0x8c, (char)0xa7, (char)0x1b, (char)0x81, (char)0xcb, (char)0x6b, (char)0xc7, (char)0x20, (char)0x45, (char)0x0e, (char)0x23, (char)0x19, (char)0xb8, (char)0xa3, (char)0x29, (char)0x29, (char)0xf4, (char)0x99, (char)0xde, (char)0xfb, (char)0xad, (char)0xa5 }; + + char randBytes[nbBytes]; + readRand(randBytes, nbBytes); + + // We discard the n most significant bits where n >= 0 && n <= 7. + if (nbBitsFirstByte != 8) + randBytes[0] &= 0xFF >> (8 - nbBitsFirstByte); + + // If asked we set the most significant bit to 1. + if (forceSize) + randBytes[0] |= 0x01 << (nbBitsFirstByte - 1); + + mpz_class n; + mpz_import(n.get_mpz_t(), nbBytes, 1, sizeof(char), 1, 0, randBytes); // Big-endian -> most significant byte first. + return n; +} + +mpz_class Rand::randLimits(const mpz_class& from, const mpz_class& to) +{ + const mpz_class nbValues = to - from + 1; + const size_t nbBits = mpz_sizeinbase(mpz_class(nbValues - 1).get_mpz_t(), 2); + + // A 'nbBytes' size random number is generated, if it matches the given limits we return it. + for (;;) + { + mpz_class n = randSize(nbBits, false) + from; + if (n >= from && n <= to) + return n; + } +} + +mpz_class Rand::randPrime(const int size_bits) +{ + mpz_class r = randSize(size_bits); + mpz_nextprime(r.get_mpz_t(), r.get_mpz_t()); + return r; +} + +void Rand::readRand(char* to, int size) +{ + const string RANDOM_SOURCE("/dev/urandom"); + + static fstream ifs(RANDOM_SOURCE, ios_base::in); + if (!ifs) + { + cerr << "Unable to read the random source: " << RANDOM_SOURCE << endl; + throw 1; + } + + ifs.read(to, size); +} diff --git a/src/Rand.h b/src/Rand.h new file mode 100644 index 0000000..2ee12a1 --- /dev/null +++ b/src/Rand.h @@ -0,0 +1,36 @@ +#ifndef RAND_H +#define RAND_H + +#include + +class Rand +{ +public: + /** + * Returns a random number with a maximum size of 'sizeBits'. + * If 'forceSize' is true the size is exactly 'sizeBits', so the highest bit will always be 1. + * + * For example, for 'sizeBits' = 12 and 'forceSize' = true, the returned number will be in the following range: + * [2^11, 2^12-1] + * + * For 'sizeBits' = 12 and 'forceSize' = false, the returned number will be in the following range: + * [0, 2^12-1] + */ + static mpz_class randSize(int sizeBits, bool forceSize = true); + + /** + * Return a random number n such as: + * 'from' <= n <= 'to' + */ + static mpz_class randLimits(const mpz_class& from, const mpz_class& to); + + static mpz_class randPrime(const int size_bits); + +private: + /** + * Read a rand from "/dev/urandom" of size 'size' in byte to the given array 'to'. + */ + static void readRand(char* to, int size); +}; + +#endif diff --git a/src/Rsa.cpp b/src/Rsa.cpp new file mode 100644 index 0000000..be21998 --- /dev/null +++ b/src/Rsa.cpp @@ -0,0 +1,47 @@ +#include "Rsa.h" + +using namespace std; + +#include "Rand.h" +#include "Utils.h" + +pair Rsa::generateRSAKeys(uint exponent, uint keySizeBits) +{ + mpz_class p, q, phi; + KeyPub kPub; + KeyPriv kPriv; + + do + { + kPub.e = exponent; + p = Rand::randPrime(keySizeBits / 2); + q = Rand::randPrime(keySizeBits / 2); + + kPriv.n = kPub.n = p * q; + phi = (p - 1) * (q - 1); + + } while (mpz_invert(kPriv.d.get_mpz_t(), kPub.e.get_mpz_t(), phi.get_mpz_t()) == 0); + +// For debugging purpose. +// print("p", p); +// print("q", q); +// print("n", kPub.n); +// print("phi", phi); +// print("d", kPriv.d); + + return make_pair(kPub, kPriv); +} + +mpz_class Rsa::sign(const mpz_class& m, const KeyPriv& kPriv) +{ + mpz_class result; + mpz_powm_sec(result.get_mpz_t(), m.get_mpz_t(), kPriv.d.get_mpz_t(), kPriv.n.get_mpz_t()); + return result; +} + +bool Rsa::verifySignature(const mpz_class& m, const mpz_class& sig, const KeyPub& kPub) +{ + mpz_class mPrime; + mpz_powm_sec(mPrime.get_mpz_t(), sig.get_mpz_t(), kPub.e.get_mpz_t(), kPub.n.get_mpz_t()); + return m == mPrime; +} diff --git a/src/Rsa.h b/src/Rsa.h new file mode 100644 index 0000000..cbc3676 --- /dev/null +++ b/src/Rsa.h @@ -0,0 +1,27 @@ +#ifndef RSA_H +#define RSA_H + +#include +#include + +class Rsa +{ +public: + struct KeyPub { + mpz_class n; + mpz_class e; + }; + + struct KeyPriv { + mpz_class n; + mpz_class d; + }; + + static std::pair generateRSAKeys(uint exponent, uint keySizeBits); + + static mpz_class sign(const mpz_class& m, const KeyPriv& kPriv); + + static bool verifySignature(const mpz_class& m, const mpz_class& sig, const KeyPub& kPub); +}; + +#endif diff --git a/src/RsaCrt.cpp b/src/RsaCrt.cpp new file mode 100644 index 0000000..43f0b97 --- /dev/null +++ b/src/RsaCrt.cpp @@ -0,0 +1 @@ +#include "RsaCrt.h" diff --git a/src/RsaCrt.h b/src/RsaCrt.h new file mode 100644 index 0000000..29bc4b9 --- /dev/null +++ b/src/RsaCrt.h @@ -0,0 +1,20 @@ +#ifndef RSACRT_H +#define RSACRT_H + +#include + +class RsaCrt +{ +public: + RsaCrt(); + + struct KeyPrivCRT { + mpz_class p; + mpz_class q; + mpz_class dp; + mpz_class dq; + mpz_class qInv; + }; +}; + +#endif diff --git a/src/Utils.cpp b/src/Utils.cpp new file mode 100644 index 0000000..b60be50 --- /dev/null +++ b/src/Utils.cpp @@ -0,0 +1,24 @@ +#include "Utils.h" + +#include +using namespace std; + +void Utils::print(string name, mpz_class value) +{ + cout << name << ": " << value << endl; +} + +Timer::Timer() : + time(chrono::high_resolution_clock::now()) +{} + +int Timer::ms() const +{ + return chrono::duration_cast(chrono::high_resolution_clock::now() - this->time).count(); +} + +ostream& operator<<(ostream& os, const Timer& t) +{ + os << t.ms() << " ms"; + return os; +} diff --git a/src/Utils.h b/src/Utils.h new file mode 100644 index 0000000..d765da0 --- /dev/null +++ b/src/Utils.h @@ -0,0 +1,29 @@ +#ifndef UTILS_H +#define UTILS_H + +#include +#include +#include + +#include + +class Utils +{ +public: + static void print(std::string name, mpz_class value); +}; + +class Timer +{ +public: + Timer(); + int ms() const; + friend std::ostream& operator<<(std::ostream& os, const Timer& t); + +private: + std::chrono::time_point time; +}; + +std::ostream& operator<<(std::ostream& os, const Timer& t); + +#endif diff --git a/src/lab3.qbs b/src/lab3.qbs new file mode 100644 index 0000000..2117c09 --- /dev/null +++ b/src/lab3.qbs @@ -0,0 +1,27 @@ +import qbs 1.0 + +Product { + name: "lab3" + type: "application" + + files: ["main.cpp", "Rand.h", "Rand.cpp", "Rsa.h", "Rsa.cpp", "RsaCrt.h", "RsaCrt.cpp", "Utils.h", "Utils.cpp"] + + cpp.commonCompilerFlags: ["-std=c++11"] + cpp.staticLibraries: ["gmp", "gmpxx"] + + Properties { + condition: qbs.buildVariant == "release" + + //cpp.commonCompilerFlags: outer.concat("") + + // Override the default optimization (-02). + cpp.optimization: "none" + cpp.cxxFlags: "-O3" + } + Properties { + condition: qbs.buildVariant == "debug" + cpp.debugInformation: true + } + + Depends { name: "cpp" } +} diff --git a/src/main.cpp b/src/main.cpp new file mode 100644 index 0000000..ac75df1 --- /dev/null +++ b/src/main.cpp @@ -0,0 +1,40 @@ +/** + * ICR - Labo 3. + * It uses GMPxx lib and C++11. + * It needs the RNG file "/dev/urandom". + * + * Author: Grégory Burri + */ + +#include +using namespace std; + +#include + +#include "Rsa.h" +#include "RsaCrt.h" + +const uint KEY_SIZE_BITS = 1024; +const uint RSA_PUBLIC_EXPONENT = 65537; + +int main(int argc, char** argv) +{ + vector args; + for (int i = 0; i < argc; i++) + args.push_back(string(argv[i])); + + const auto& keys = Rsa::generateRSAKeys(RSA_PUBLIC_EXPONENT, KEY_SIZE_BITS); + const auto& kPub = keys.first; + const auto& kPriv = keys.second; + + mpz_class message(42); + mpz_class signature = Rsa::sign(message, kPriv); + + mpz_class message2(42); + cout << "verify: " << Rsa::verifySignature(message2, signature, kPub) << endl; + + mpz_class message3(43); + cout << "verify: " << Rsa::verifySignature(message3, signature, kPub) << endl; + + return 0; +}