wiener.cpp

C++ implementaion for RSA together with the Wiener attack. It uses NTL library for big numbers

#include "Wiener.h"

#include <iostream>

using namespace std;

//***************************************************************
// Construtors
//***************************************************************
Wiener::Wiener()
{

}

Wiener::~Wiener(void)
{
}

//***************************************************************
// Atack function
//***************************************************************

// Calculate Q, Alfa, Beta
//	 e = q1 *  n + r1;
//	 n = q2 * r1 + r2;
//	r1 = q3 * r2 + r3;
//  .....
//  r_(k-2) = qk * r_(k-1) + rk;
//  r_(k-1) = q_(k+1) * rk
//
// alfa1 = q1
// alfa2 = q1 * q2 + 1
// alfai = qi * alfa_(i-1) + alfa_(i-2)
//
// beta1 = 1
// beta2 = q2
// betai = qi * beta_(i-1) + beta_(i-2)
void Wiener::Calculate()
{

	NTL::ZZ qi1, qi2, qi3;
	NTL::ZZ alfai1, alfai2, alfai3;
	NTL::ZZ betai1, betai2, betai3;
	NTL::ZZ rem, rem1, rem2;

	rem1 = m_rsaKey.E;
	rem2 = m_rsaKey.N;
	NTL::DivRem(qi1, rem, rem1, rem2);
	
	rem1 = rem2;
	rem2 = rem;
	NTL::DivRem(qi2, rem, rem1, rem2);
	rem1 = rem2;
	rem2 = rem;

	alfai1 = qi1;
	alfai2 = qi1 * qi2+ 1;

	betai1 = 1;
	betai2 = qi2;

	if(Criterion(alfai2, betai2))
	{
			m_result.D = betai2;
			m_result.PhiN = (m_rsaKey.E * m_result.D - 1) / alfai2;
			cout << "\n -------- K " << m_nK << '\n';
			return;
	}
	m_nK = 2;

	//cout << "Q -  " << qi1 << '\n';
	//cout << "Alfa -- " << alfai1 << '\n';
	//cout << "Beta -----" << betai1 << '\n';
	//cout << "Q -  " << qi2 << '\n';
	//cout << "Alfa -- " << alfai2 << '\n';
	//cout << "Beta -----" << betai2 << '\n';
	while (rem != 0)
	{
		NTL::DivRem(qi3, rem, rem1, rem2);		
		rem1 = rem2;
		rem2 = rem;

		alfai3 = qi3 * alfai2 + alfai1;
		alfai1 = alfai2;
		alfai2 = alfai3;

		betai3 = qi3 * betai2 + betai1;
		betai1 = betai2;
		betai2 = betai3;
		
		//cout << "Q -  " << qi3 << '\n';
		//cout << "Alfa -- " << alfai3 << '\n';
		//cout << "Beta -----" << betai3 << '\n';
		if(Criterion(alfai3, betai3))
		{
			m_result.D = betai3;
			m_result.PhiN = (m_rsaKey.E * m_result.D - 1) / alfai3;
			//cout << "\n -------- K " << m_nK << '\n';
			m_result.Succeded = true;
			return;
		}

		m_nK++;
	}
	//cout << "\n not good " << m_nK << '\n';

	m_result.Succeded = false;

}

// The criterion is:
// the system:
//		x*y = key.N
//		(x-1)*(y-1) = (key.E * D - 1)/ L
// must have solution from Z;
// the system is eqv to
// y = ((+-)sqrt(delta) - b) / 2 is natural -> one sol is Q , other is P
//			where delta = b*b - 4*key.N with b = ((key.e * D - 1) / L) - N - 1
bool Wiener::Criterion(const NTL::ZZ& L, const NTL::ZZ& D)
{
	NTL::ZZ b;
	NTL::ZZ delta;

	if (NTL::divide(b, (m_rsaKey.E * D - 1), L) == 0)
		return false;

	b = b - m_rsaKey.N - 1;

	if ( (delta = b * b - (4 * m_rsaKey.N)) < 0)
		return false;

	NTL::ZZ y;
	NTL::ZZ sqrtDelta;

	NTL::SqrRoot(sqrtDelta, delta);
	if ( NTL::sqr(sqrtDelta) != delta)
		return false;

	m_result.P = sqrtDelta - b;
	if (NTL::IsOdd(sqrtDelta))
	{
		m_result.P = 0;
		return false;
	}

	m_result.P = m_result.P / 2;
	m_result.Q = (-sqrtDelta - b ) / 2;
	
	return true;

}
//***************************************************************
// Interface
//***************************************************************
Wiener::WienerResult Wiener::Atack(const RSACryptoSystem::PublicKey &key)
{
	m_rsaKey.E = key.E;
	m_rsaKey.N = key.N;

	m_result.Succeded = false;
	Calculate();

	return m_result;
}

void Wiener::PrintAtackResults() const
{
	cout << "\nAtack Result on Key : ";
	cout << "\nN : " << m_rsaKey.N;
	cout << "\nE : " << m_rsaKey.E;
	if (m_result.Succeded)
	{
		cout << "\n\tD : " << m_result.D;
		cout << "\n\tP : " << m_result.P;
		cout << "\n\tQ : " << m_result.Q;
		cout << "\n\tPhi(N) : " << m_result.PhiN << '\n';
	}
	else
	{
		cout << "\n They key couldn't be broken\n" << '\n';
	}

}