4. (RSA:) manchmal, aber nur manchmal...

(RSA:) manchmal, aber nur manchmal...


  • Hi,

    ich steh wahrscheinlich auf irgendwelchen Leitungen herum... Folgender Code liefert manchmal gültige, manchmal ungültige (im sinne von e * d + k * phi == 1 ) Werte für RSA Public und Private key:

    #include <stdbool.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

typedef struct {

	long exponent;
	long module;

} key_t;

bool is_prime( long number )
{
	long i = 2, max = ( long ) sqrt( number );

	for( ; i <= max; ++i ) {

		if( !( number % i ) ) {

			return false;
		}
	}

	return true;
}

long get_rand_prime( void )
{
	long number = 0;

	do {

		number = 10 + rand( ) % 100;

	} while( !is_prime( number ) );

	return number;
}

// cgd( a, b ) = s * a + t * b
long extended_euklid( long a, long b, long *s, long *t )
{
	long quotient, remainder;
	long s1 = 0, s2 = 1;
	long t1 = 1, t2 = 0;

	if( !b ) {

		*s = 1;
		*t = 0;

		return a;
	}

	while( b ) {

		quotient = a / b;
		remainder = a - quotient * b;

		*s = s2 - quotient * s1;
		*t = t2 - quotient * t1;

		a = b;
		b = remainder;

		s2 = s1;
		s1 = *s;

		t2 = t1;	
		t1 = *t;
	}

	*s = s2;
	*t = t2;

	return a;
} 

void rsa_generate_keys( key_t *public_key, key_t *private_key )
{
	long p = get_rand_prime( ), q = get_rand_prime( );
	long N = p * q;
	long phi = ( p - 1 ) * ( q - 1 );
	long e = phi - 1;
	long d = 0;
	long k = 0;

	do {

		e = 1 + ( rand( ) % phi - 1 );

	} while( !( phi % e ) );

	// e * d + k * phi = 1 = cgd( e, phi ) =
	extended_euklid( e, phi, &d, &k );

	printf( "p = %i\nq = %i\nN = %i\nphi = %i\ne = %i\nd = %i\n", p, q, N, phi, e, d );

	if(  e * d + k * phi == 1 ) {

		printf( "\n! jup !" );
	}
}

int main( )
{
	key_t rsa_public_key = { 0 }, rsa_private_key = { 0 };

	srand( ( unsigned int ) time( 0 ) );
	rsa_generate_keys( &rsa_public_key, &rsa_private_key );
}

    vielleicht hat jemand bessere Augen als ich 😉

    cheers, Swordfish

    0
  • M

    Dein Fehler liegt wohl in Zeile 94.

    Hier brichst du die While-Schleife ab, sobald du zwei Zahlen
    e und phi gefunden hast, wobei e kein Teiler von phi ist.

    Dies sagt aber noch nicht aus, dass der größte gemeinsame Teiler (ggt,
    in english: gcd und nicht cgd) gleich 1 ist.

    Dies setzt du dann aber in deiner if-Anweisung in Zeile 101 voraus.

    Gruß mcr

    EDIT: nun sollte es für dich ein leichtes sein, deinen Code zu verbessern

    0

  • mcr schrieb:

    Dein Fehler liegt wohl in Zeile 94.

    aja, stimmt. Ich hab' in der Wiki zu schnell d'rübergelesen. Dort heißt es

    [...]
    4) Wähle eine zu phi( N ) teilerfremde Zahl e, für die gilt, 1 < e < phi( N ).

    Ich habe einen Teiler e von phi( N ) gesucht, nicht ein e das keine gemeinsamen Teiler mit phi( N ) hat, also relativ prim zu phi( N ) ist. 🤡

    Danke 😉

    cheers, Swordfish

    0
Anmelden zum Antworten