Hi everyone,I'm tryind to do something about sound on linux.I basically record some sound and try to encyrpt it using algorithm.However,I encountered some sort of pointer problem.Both RSA algorithm and recording&listenin sound works properly.
Here is my code:

/*
 * rsa.c
 *
 *  Created on: 24 May 2012
 *      Author: tugce
 */


#include <stdio.h>
#include <ncurses.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <math.h>
#include<fcntl.h>
#include<stdlib.h>
#include<stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/types.h>
#include <sys/ioctl.h>
#include <stdlib.h>
#include <stdio.h>
#include <linux/soundcard.h>

#define LENGTH 3    /* how many seconds of speech to store */
#define RATE 8000   /* the sampling rate */
#define FILE_INPUT "/dev/dsp" /* Path to the sound card. */
#define FILE_OUTPUT "/dev/dsp"

//Her is gcd function
int gcd(int a,int b)
{
    while(a!=b){

        if(a>b)
            a-=b;
        else
            b-=a;
    }
    return a;
}


//This is called  Extended Euclid’s Algorithm to find d.

int findD(int e,int n)
{

    int f=e;
    int d=n;

    int x1, x2, x3, y1, y2, y3;
    x1 = 1; x2 = 0; x3 = f; //p
    y1 = 0; y2 = 1; y3 = d; //d



    int q = 0, i = 1;
    int t1 = 0, t2 = 0, t3 = 0;
    do
    {
        if (i == 1)
        {
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        else
        {
            x1 = y1; x2 = y2; x3 = y3;
            y1 = t1; y2 = t2; y3 = t3;
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        i++;


        if (y3 == 0)
        {
            break;
        }

    } while (y3 != 1);

    if (y3 == 0)
    {
        //printf("Sayinin tersi yoktur!!!!");
    }
    else
    {
        // printf("\nSayinin tersi : %d" , y2);
    }

    if(y2<=0)
    {

        y2=e+y2;

    }
    return y2;

}

//Instead of using pow function,I have choose to write square and multiply method which is faster and
//more suitable for big integers.Because we have no such a change to find 104^30 such like that
//Here computes pow(a,b)%n
int squareMul(int a,int b,int n)
{

    int y = 1;

    /*  Compute pow(a, b) % n using the binary square and multiply method. */
    while (b != 0)
    {
        /*  For each 1 in b, accumulate y. */
        if (b & 1)
        {
            y = (y * a) % n;
        }

        /* Square a for each bit in b. */
        a = (a * a) % n;

        /*  Prepare for the next bit in b. */
        b = b >> 1;
    }

    return y;

}
//Encyrption function
//Assume our plain-text is M
int *encyrpt(int text[],int e,int n)
{

    int t=0;
    int *s=(int *)malloc(24000);

    for(t=0;t<sizeof(text);t++)
    {
        int gec=(int)text[t];

        //Here computes E(M)=M^e mod n;
        s[t]=squareMul(gec,e,n);

    }


    return s;


}

//Here is decyrption
//Assume our chipher-text is C
int *decyrpt(int enc[],int d,int e,int n)
{
    int i=0;
    int *s=(int *)malloc(24000);

    for(i=0;i<sizeof(enc);i++)
    {
        int gelenEnc=(int)enc[i];
        //Here computes D(C)=C^d mod n;
        s[i]=squareMul(gelenEnc,d,n);


    }
    return s;

}



//Here is totient function to find prime to  m.
int totient(int m)
{

    int i;
    int ph=1;
    for(i=2;i<m;i++){

        if(gcd(i,m)==1)
        {
            ph=i;
            break;

        }
    }
    return ph;

}

int main(){

    int sound_device;

      /* open sound device */
    sound_device = open("/dev/dsp", O_RDWR);
    if (sound_device < 0) {
    perror("Open sound card failed");
    exit(1);
     }

    //Here are some variables that I used for RSA ALGORİTHM

    int* ascii;
    int* enc;
    int* dec;
    int p,q;
    int k=0;
    int n;
    int e;
    int c;
    int phi;
    int d;
    unsigned char buf[LENGTH*RATE];





    //Here enter 2 relatively prime number
    //I have chose the p=73 and q=151

    p=73;
    q=151;

    printf("\n\ p :%d and q :%d \t \n",p,q);
    //Here computes n
    n = p*q;
    //Here computes phi func simply
    phi=(p-1)*(q-1);

    printf("\n\ n :\t= %d \n",n);
    printf("\n\ Phi :\t= %d \n",phi);

    //Here Euilers Totient function.It finds a number 'e' which is relatively prime with phi.
    e=totient(phi);
    //Here computes d,which is multiplicative inverse of e modula phi.
    d=findD(phi,e);

    printf("\n\ e :\t= %d  \n",e);

    printf("\n\ d :\t= %d which is multiplicative inverse of e modula phi \n",d);




     printf("Say something:\n");
    read(sound_device, buf, sizeof(buf)); /* record some sound */

    //Here is the ascii values for plainText.I have created new array in order to store plainText's ascii for simplicty
    ascii=(int *)malloc(24000*sizeof(int));
    enc=(int *)malloc(24000*sizeof(int));   
    dec=(int *)malloc(24000*sizeof(int));

    //Here ascii stores plaintText's ascii number.
    for(c=0;c<LENGTH*RATE;c++)
    {

        int k=(int)buf[c];

        ascii[c]=k;
        printf("\n\t Ascii's of %c  \t= %d  \n",buf[c],ascii[c]);
    }


    //Here is encyription
    enc=encyrpt(ascii,e,n);


    //Here is decyription
    dec=decyrpt(enc,d,e,n);

    write(sound_device, dec, LENGTH*RATE);
     ioctl(sound_device, SOUND_PCM_SYNC, 0); 
    for(k=0;k<sizeof(dec);k++)
    {

        printf("%c",dec[k]);

    }

}

Basically,Rsa works with ascii array which includes char's of my word and encyrpt/decyrpt asciis with rsa.Here is my RSA algorithm which works properly separate with sound.

/*
 * rsa.c
 *
 *  Created on: 24 May 2012
 *      Author: tugce
 */


#include <stdio.h>
#include <ncurses.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

//Her is gcd function
int gcd(int a,int b)
{
    while(a!=b){

        if(a>b)
            a-=b;
        else
            b-=a;
    }
    return a;
}


//This is called  Extended Euclid’s Algorithm to find d.

int findD(int e,int n)
{

    int f=e;
    int d=n;

    int x1, x2, x3, y1, y2, y3;
    x1 = 1; x2 = 0; x3 = f; //p
    y1 = 0; y2 = 1; y3 = d; //d



    int q = 0, i = 1;
    int t1 = 0, t2 = 0, t3 = 0;
    do
    {
        if (i == 1)
        {
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        else
        {
            x1 = y1; x2 = y2; x3 = y3;
            y1 = t1; y2 = t2; y3 = t3;
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        i++;


        if (y3 == 0)
        {
            break;
        }

    } while (y3 != 1);

    if (y3 == 0)
    {
        //printf("Sayinin tersi yoktur!!!!");
    }
    else
    {
        // printf("\nSayinin tersi : %d" , y2);
    }

    if(y2<=0)
    {

        y2=e+y2;

    }
    return y2;

}

//Instead of using pow function,I have choose to write square and multiply method which is faster and
//more suitable for big integers.Because we have no such a change to find 104^30 such like that
//Here computes pow(a,b)%n
int squareMul(int a,int b,int n)
{

    int y = 1;

    /*  Compute pow(a, b) % n using the binary square and multiply method. */
    while (b != 0)
    {
        /*  For each 1 in b, accumulate y. */
        if (b & 1)
        {
            y = (y * a) % n;
        }

        /* Square a for each bit in b. */
        a = (a * a) % n;

        /*  Prepare for the next bit in b. */
        b = b >> 1;
    }

    return y;

}
//Encyrption function
//Assume our plain-text is M
int *encyrpt(int text[],int e,int n)
{

    int t=0;
    int *s=(int *)malloc(100);

    for(t=0;t<sizeof(text);t++)
    {
        int gec=(int)text[t];

        //Here computes E(M)=M^e mod n;
        s[t]=squareMul(gec,e,n);

    }


    return s;


}

//Here is decyrption
//Assume our chipher-text is C
int *decyrpt(int enc[],int d,int e,int n)
{
    int i=0;
    int *s=(int *)malloc(100);

    for(i=0;i<sizeof(enc);i++)
    {
        int gelenEnc=(int)enc[i];
        //Here computes D(C)=C^d mod n;
        s[i]=squareMul(gelenEnc,d,n);


    }
    return s;

}



//Here is totient function to find prime to  m.
int totient(int m)
{

    int i;
    int ph=1;
    for(i=2;i<m;i++){

        if(gcd(i,m)==1)
        {
            ph=i;
            break;

        }
    }
    return ph;

}

int main(){
    //Here are some variables that I used for RSA ALGORİTHM
    //str is our plain-text
    char *plainText;
    int *ascii;
    int *enc;
    int *dec;
    int p,q;
    int k=0;
    int n;
    int e;
    int c;
    int phi;
    int d;

    plainText="Merhaba";

    //Here enter 2 relatively prime number
    //I have chose the p=73 and q=151

    p=73;
    q=151;

    printf("\n\ p :%d and q :%d \t \n",p,q);
    //Here computes n
    n = p*q;
    //Here computes phi func simply
    phi=(p-1)*(q-1);

    printf("\n\ n :\t= %d \n",n);
    printf("\n\ Phi :\t= %d \n",phi);

    //Here Euilers Totient function.It finds a number 'e' which is relatively prime with phi.
    e=totient(phi);
    //Here computes d,which is multiplicative inverse of e modula phi.
    d=findD(phi,e);

    printf("\n\ e :\t= %d  \n",e);

    printf("\n\ d :\t= %d which is multiplicative inverse of e modula phi \n",d);


    //Here is the ascii values for plainText.I have created new array in order to store plainText's ascii for simplicty
    ascii=(int *)malloc(sizeof(int)*sizeof(plainText)/sizeof(char));

    //Here ascii stores plaintText's ascii number.
    for(c=0;c<7;c++)
    {

        int k=(int)plainText[c];

        ascii[c]=k;
        printf("\n\t Ascii's of %c  \t= %d  \n",plainText[c],ascii[c]);
    }


    //Here is encyription
    enc=encyrpt(ascii,e,n);

    /*for(k=0;k<sizeof(enc);k++)
    {

        printf(" Encyprted : %d\n  ",*(enc+k));

    }*/

    //Here is decyription
    dec=decyrpt(enc,d,e,n);


    for(k=0;k<sizeof(dec);k++)
    {

        printf("%c",dec[k]);

    }


}

Here is writing&listening from sound card.It'S also works properly.

#include <sys/ioctl.h>
#include <stdlib.h>
#include <stdio.h>
#include <linux/soundcard.h>

#define LENGTH 3    /* how many seconds of speech to store */
#define RATE 8000   /* the sampling rate */


/* this buffer holds the digitized audio */
unsigned char buf[LENGTH*RATE];

#define FILE_INPUT "/dev/dsp" /* Path to the sound card. */
#define FILE_OUTPUT "/dev/dsp"


int main() {
    int sound_device;

      /* open sound device */
    sound_device = open("/dev/dsp", O_RDWR);
    if (sound_device < 0) {
    perror("Open sound card failed");
    exit(1);
     }




    /*Read samples from the soundcard into buffer. (Blocking function call)*/
    //read(sound_device, buffer, LENGTH);

    while(1)
    {    printf("Say something:\n");
        read(sound_device, buf, sizeof(buf)); /* record some sound */
        printf("You said:\n");
        write(sound_device, buf, sizeof(buf));
        ioctl(sound_device, SOUND_PCM_SYNC, 0); 

    }



    return 1;

}

I'm new with C language,so I've little idea how to deal with arrays&sizes etc.Therefore I didnt combined both RSA and sound algortihms in 1 one code.Any help would be appriciated.

Thanks

Hi everyone,I'm tryind to do something about sound on linux.I basically record some sound and try to encyrpt it using algorithm.However,I encountered some sort of pointer problem.Both RSA algorithm and recording&listenin sound works properly.
- - -
Basically,Rsa works with ascii array which includes char's of my word and encyrpt/decyrpt asciis with rsa.Here is my RSA algorithm which works properly separate with sound.
- - -
Here is writing&listening from sound card.It'S also works properly.
- - -
I'm new with C language,so I've little idea how to deal with arrays&sizes etc.Therefore I didnt combined both RSA and sound algortihms in 1 one code.Any help would be appriciated.

OK, you say all your parts work properly.
You don't know how to deal with arrays and sizes (so how can it work properly?)
You encounter "some sort of pointer problem"
Then you post almost 600 lines of code with no explanation.
How are we supposed to locate "some sort of pointer problem" with no clue where to look nor what to look for?

I said "Therefore I didnt combined both RSA and sound algortihms in 1 one code."

I have tried in first code but it does not work.In order to you see working algorithms RSa algortihm and writing to sound card,I have send last 2 code to you.

> printf("Say something:\n");
>     read(sound_device, buf, sizeof(buf)); /* record some sound */
>     //Here is the ascii values for plainText.I have created new array in order to store plainText's ascii for simplicty
>     ascii=(int *)malloc(24000*sizeof(int));
>     enc=(int *)malloc(24000*sizeof(int));   
>     dec=(int *)malloc(24000*sizeof(int));
>     //Here ascii stores plaintText's ascii number.
>     for(c=0;c<LENGTH*RATE;c++)
>     {
>         int k=(int)buf[c];
>         ascii[c]=k;
>         printf("\n\t Ascii's of %c  \t= %d  \n",buf[c],ascii[c]);
>     }
>     //Here is encyription
>     enc=encyrpt(ascii,e,n);
>     //Here is decyription
>     dec=decyrpt(enc,d,e,n);
>     write(sound_device, dec, LENGTH*RATE);
>      ioctl(sound_device, SOUND_PCM_SYNC, 0); 
>     for(k=0;k<sizeof(dec);k++)
>     {
>         printf("%c",dec[k]);
>     }

Here my main problem.

I think I did not do allocations for ascii,en,dec pointers correctly.Therefore no sound occurs.

Basically I need some code that is it reserves some int array depending the size of buffer which is char, and then send this int array to enc function and that returns int array.In main, want to hold to returning int array from enc function another int array.
Thanks

dont use sizeof. do track memmory manually or use static buffers for now, and if everything works, try to change them

Edited 4 Years Ago by Sokurenko: fix

First off, you might want to use calloc() rather than malloc() for allocating arrays:

ascii=(int *)calloc(24000, sizeof(int));

It's a minor point, as there is no real difference in it result-wise, but it does make it clearer what your intent is.

Also, you are allocating memory and having enc and dec point to it, but then you assign the values of the encryption and decryption functions to those same pointers; the allocated memory is being lost, and the pointers reassigned to the new buffers allocated by the functions. This doesn't really impact the program (aside from creating a massive memory leak), but it should still be fixed.

Third, in the line

for(k=0;k<sizeof(dec);k++)

the sizeof operator is acting on an int pointer (dec), not the memory which the pointer refers to. Thus, the result of sizeof(dec) is the size of the pointer (probably either 4 or 8 bytes, depending on whether you are using a 32-bit or 64-bit Linux), not that of the buffer it points to.

Getting to the meat of the problem, we find all three of these points to be relevant to the encyrpt() function:

int *encyrpt(int text[],int e,int n)
{
    int t=0;
    int *s=(int *)malloc(24000);
    for(t=0;t<sizeof(text);t++)
    {
        int gec=(int)text[t];
        //Here computes E(M)=M^e mod n;
        s[t]=squareMul(gec,e,n);
    }
    return s;
}

Here, the allocation size appears to be wrong; you are allocating 24000 bytes, but passing this to an int*. The result is that you get 6000 integer values (assuming a 32-bit int), rather than the 24000 you appear to want. Had you used calloc(), you wouldn't have overlooked the variable size component.

Also, you are getting the size of the text[] buffer using sizeof. While you used the array syntax for declaring text[], the variable itself is actually a pointer, as it would not have the size of the actual text buffer on hand at compile time. Thus, sizeof(text) gives the pointer size, not the buffer size. You would need to pass the size of the actual buffer to the function separately to get the correct result.

For that matter, you presumably want the actual ciphertext buffer to be the same size (or some factor thereof) as the plaintext, so allocating a fixed size buffer isn't necessarily what you want. It would make more sense to match the size of the text buffer:

int *encrypt(int text[], int text_size, int e, int n)
{
    int t = 0;
    int *s = (int *)calloc(text_size, sizeof int);

    for(t = 0; t < text_size; t++)
    {
        //Here computes E(M)=M^e mod n;
        s[t] = squareMul(text[t], e, n);
    }

    return s;
}

(Note the corrected spelling for 'encrypt', BTW). This may fix some subtle bugs that did not show up in your tests, but which were causing the problems with the final program. Comments and corrections welcome.

Edited 4 Years Ago by Schol-R-LEA

I'd like to give you two more pieces of advice: first, separate the encryption and decryption code from the sound card code, and the sound card code from the main() function, and compile them separately, linking them together only once you tested the two library sections.

Second, you really want to trim your #includes; you have multiple entries for a number of libraries, and some libraries are included which you don't seem to need at all. Breaking the code up will help with this, as (to give one example) the main() function wouldn't need to include <math.h>, while the cipher code wouldn't need the Linux-specific <fctrl.h> and <linux/soundcard.h> headers.

I've done some experimenting with your code, and modified it somewhat for testing, but I found serious issues with it. The test code I came up with is as follows:

rsamath.h

/* rsamath.h */

#ifndef RSAMATH_H
#define RSAMATH_H

int gcd(int a,int b);
int findD(int e,int n);
int squareMul(int a,int b,int n);
int totient(int m);

#endif

rsamath.c

/*
 * rsamath.c
 *
 *  Created on: 24 May 2012
 *      Author: tugce
 */

#include "rsamath.h"

/*Here is gcd function */
int gcd(int a,int b)
{
    while(a!=b){
        if(a>b)
            a-=b;
        else
            b-=a;
    }
    return a;
}

/*This is called  Extended Euclid’s Algorithm to find d. */
int findD(int e,int n)
{
    int f=e;
    int d=n;
    int x1, x2, x3, y1, y2, y3;
    int q = 0, i = 1;
    int t1 = 0, t2 = 0, t3 = 0;

    x1 = 1; x2 = 0; x3 = f;
    y1 = 0; y2 = 1; y3 = d;

    do
    {
        if (i == 1)
        {
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        else
        {
            x1 = y1; x2 = y2; x3 = y3;
            y1 = t1; y2 = t2; y3 = t3;
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        i++;
        if (y3 == 0)
        {
            break;
        }
    } while (y3 != 1);
    if(y2<=0)
    {
        y2=e+y2;
    }
    return y2;
}

/*Instead of using pow function,I have choose to write square and multiply method which is faster and
* more suitable for big integers.Because we have no such a change to find 104^30 such like that
* Here computes pow(a,b)%n */
int squareMul(int a,int b,int n)
{
    int y = 1;
    /*  Compute pow(a, b) % n using the binary square and multiply method. */
    while (b != 0)
    {
        /*  For each 1 in b, accumulate y. */
        if (b & 1)
        {
            y = (y * a) % n;
        }
        /* Square a for each bit in b. */
        a = (a * a) % n;
        /*  Prepare for the next bit in b. */
        b = b >> 1;
    }
    return y;
}

/* Here is totient function to find prime to  m. */
int totient(int m)
{
    int i;
    int ph=1;
    for(i=2;i<m;i++){
        if(gcd(i,m)==1)
        {
            ph=i;
            break;
        }
    }
    return ph;
}

rsa.h

/* rsa.h */

#ifndef RSA_H
#define RSA_H


char *encrypt(char* text, int text_size, int e, int n);
char *decrypt(char* enc, int text_size, int d, int n);

#endif

rsa.c

/*
 * rsa.c
 *
 *  Created on: 24 May 2012
 *      Author: tugce
 */

#include "rsamath.h"
#include "rsa.h"
#include <malloc.h>

/* Encryption function
 * Assume our plain-text is M */
char *encrypt(char text[], int text_size, int e, int n)
{
    int t = 0;
    char *s;

    s = calloc(text_size, sizeof (char));
    for(t = 0; t < text_size; t++)
    {
        /*Here computes E(M)=M^e mod n; */
        s[t] = squareMul(text[t], e, n);
    }
    return s;
}

/* Here is decryption
 * Assume our cipher-text is C */
char *decrypt(char enc[], int text_size, int d, int n)
{
    int i = 0;
    char *s;

    s = calloc(text_size, sizeof (char));
    for(i = 0; i < text_size; i++)
    {
        /* Here computes D(C)=C^d mod n; */
        s[i] = squareMul(enc[i], d, n);
    }
    return s;
}

rsatest.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include "rsamath.h"
#include "rsa.h"

#define MAXINT 2147483648

int main()
{
    int a, b, c;
    char plaintext[] = "Lorem ipsum dolor sit amet, consectetur adipisicing elit\n";
    char* ciphertext;
    char* final_text;
    int e, n, size;

    size = strlen(plaintext);
    srand(time(NULL));

    a = rand() % 32;
    b = rand() % 8;
    c = squareMul(a, b, MAXINT);

    printf("%d ** %d = %d\n\n", a, b, c);

    e = rand();
    n = rand();

    ciphertext = encrypt(plaintext, size, e, n);
    final_text = decrypt(ciphertext, size, e, n);

    printf("%s", final_text);

    free(ciphertext);
    free(final_text);

    return 0;
}

_ Running this test shows that the character-based version of the encryption and/or decryption techniques do not seem to work, at least not with the random seeds I've been using. It may be, however, that the randomly generated keys are too large for the integer operations in question, especially squareMul(), which goes out of bounds quite quickly. Another possibility is that I may simply have misunderstood the algorithm, and either misapplied it, or changed it in some way that broke it. Nonetheless, I thought you would want to know the results of my tests.

Edited 4 Years Ago by Schol-R-LEA: Added include guards to headers.

At the risk of completely highjacking this thread, I have been working on getting my own version of this code going, and have had a certain amount of success. However, I wanted to change the key generation to use generated primes based on a passphrase, rather than the constant primes of the original. It is in my primality tester that I seem to be running into trouble; no matter how many candidates I test, it never comes up with a possible prime. The tester is based on the Miller-Rabin algorithm as given on Wikipedia, with some changes based on the Python implementation on Rosetta Code.

My current code is as follows:

rsamath.c

/*
* rsamath.c
*
* Created on: 24 May 2012
* Author: tugce
* modified by J. Osako 12 June 2012
*/
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include "rsamath.h"

/* generate a 64-bit unsigned random number */
uint64_t rand_u64()
{
    return ((uint64_t) rand() + (((uint64_t) rand()) << 32));
}


/* Miller-Rabin probabalistic test for primeness */
bool prime(uint64_t candidate, uint64_t iterations)
{
    uint64_t i;
    uint64_t d, s, a, a_prime, x;

    if (candidate <= 3)
    {
        return true;
    }

    if (candidate % 2 == 0)
    {
        return false;
    }

    /* determine usable values for s and d */
    s = 0;
    d = candidate - 1;

    while (d % 2 != 1)
    {
        s += 1;
        d /= 2;
    }

    if ((squareMul(2, s, UINT64_MAX) * d) != (candidate - 1))
    {
        return false;
    }


    /* run for an arbirary number of tests */
    for (i = 0; i < iterations; i++)
    {
        a = (rand_u64() + 2) % (candidate - 2);
        a_prime = squareMul(a, d, UINT64_MAX);
        x = a_prime % candidate;
        if ((x == 1) || (x == candidate - 1))
        {
            continue;
        }
        else
        {
            return !(test_composite(a, d, s, candidate));
        }
    }

    return true;
}

bool test_composite(uint64_t a, uint64_t d, uint64_t s, uint64_t n)
{
    unsigned int i;

    if (squareMul(a, d, n) == 1)
    {
        return false;
    }
    else
    {
        for (i = 0; i < s; i++)
        {
            if (squareMul(a, squareMul(2, i * d, UINT64_MAX), n) == n -1)
            {
                return false;
            }
        }
    }

    return true;
}

/*Here is gcd function */
uint64_t gcd(uint64_t a, uint64_t b)
{
    while(a!=b)
    {
        if(a>b)
            a-=b;
        else
            b-=a;
    }
    return a;
}

/*This is called Extended Euclid’s Algorithm to find d. */
uint64_t findD(uint64_t e,uint64_t n)
{
    uint64_t f=e;
    uint64_t d=n;
    uint64_t x1, x2, x3, y1, y2, y3;
    uint64_t q = 0, i = 1;
    uint64_t t1 = 0, t2 = 0, t3 = 0;
    x1 = 1;
    x2 = 0;
    x3 = f;
    y1 = 0;
    y2 = 1;
    y3 = d;
    do
    {
        if (i == 1)
        {
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        else
        {
            x1 = y1;
            x2 = y2;
            x3 = y3;
            y1 = t1;
            y2 = t2;
            y3 = t3;
            q = x3 / y3;
            t1 = x1 - (q * y1);
            t2 = x2 - (q * y2);
            t3 = x3 - (q * y3);
        }
        i++;
        if (y3 == 0)
        {
            break;
        }
    }
    while (y3 != 1);
    if(y2<=0)
    {
        y2=e+y2;
    }
    return y2;
}

/*Instead of using pow function,I have choose to write square and multiply method which is faster and
* more suitable for big integers.Because we have no such a change to find 104^30 such like that
* Here computes pow(a,b)%n */
uint64_t squareMul(uint64_t a,uint64_t b,uint64_t n)
{
    uint64_t y = 1;
    /* Compute pow(a, b) % n using the binary square and multiply method. */
    while (b != 0)
    {
        /* For each 1 in b, accumulate y. */
        if (b & 1)
        {
            y = (y * a) % n;
        }
        /* Square a for each bit in b. */
        a = (a * a) % n;
        /* Prepare for the next bit in b. */
        b = b >> 1;
    }
    return y;
}

/* Here is totient function to find prime to m. */
uint64_t totient(uint64_t m)
{
    uint64_t i;
    uint64_t ph=1;

    for(i=2; i<m; i++)
    {
        if(gcd(i,m)==1)
        {
            ph=i;
            break;
        }
    }
    return ph;
}

Note that I changed all of the values from basic ints to uint64_t, on the basis that there would be too many overflows otherwise. The key-generating code and my current version of the encryption/decryption routines are as follows:

/*
* rsa.c
*
* Created on: 24 May 2012
* Author: tugce
*/
#include "rsamath.h"
#include "rsa.h"
#include <stdlib.h>
#include <malloc.h>


/* key generation function */
struct key_pair* generate_keys(char* keyphrase)
{
    struct key_pair* keys;
    int seed = 1;
    unsigned int i;
    uint64_t p, q, phi, test, n;

    keys = (struct key_pair *) malloc(sizeof(struct key_pair));

    /* hash the keyphrase to generate a 'randomness' seed */
    for (i = 0; i < strlen(keyphrase); i++)
    {
        seed = (keyphrase[i] * seed) % 65535;
    }

    getchar();

    srand(seed);

    /* repeatedly generate random values for p and q until both are probably prime */
    do
    {
        p = rand_u64();
        if ((p % 2) == 0)
        {
            p--;   /* make sure p is not even */
        }

    } while(!prime(p, 1));

    do
    {
        q = rand_u64();
        if ((q % 2) == 0)
        {
            q--;   /* make sure q is not even */
        }
    } while(!prime(q, 1));


    n = p * q;

    phi = (p - 1) * (q - 1);

    keys->public_key = totient(phi);
    keys->private_key = findD(phi, keys->public_key);
    keys->modulus = n;
    return keys;
}

/* Encryption function
* Assume our plain-text is M */
uint64_t *encrypt(uint8_t* text, uint64_t text_size, uint64_t e, uint64_t n)
{
    unsigned int t = 0;
    uint64_t *s;

    s = (uint64_t *) calloc(text_size, sizeof (uint64_t));

    for(t = 0; t < text_size; t++)
    {
        /*Here computes E(M)=M^e mod n; */
        s[t] = squareMul(text[t], e, n);
    }
    return s;
}


/* Here is decryption
* Assume our cipher-text is C */
uint8_t *decrypt(uint64_t* enc, uint64_t text_size, uint64_t d, uint64_t n)
{
    unsigned int i = 0;
    uint8_t *s;

    s = (uint8_t *)calloc(text_size, sizeof (uint8_t));

    for(i = 0; i < text_size; i++)
    {
        /* Here computes D(C)=C^d mod n; */
        s[i] = squareMul(enc[i], d, n);
    }
    return s;
}

The encryption and decryption do apear to work when given suitable keys, but generating the keys is the problem I am now having. Getting more eyes on the prime() function would be a great help right now.

Edited 4 Years Ago by Schol-R-LEA

I am beginniong to suspect that the problwem lies with my randomization function. Is there some bias in it that I am not seeing?

/* generate a 64-bit unsigned random number */
uint64_t rand_u64()
{
return ((uint64_t) rand() + (((uint64_t) rand()) << 32));
}

Setting aside the encryption code for the moment, I took a look at the sound card code, and found something potentially problematic. The program as written uses /dev/dsp, which is the OSS sound device; but most modern Linux distros use ALSA for sound support, and not all of them have backwards compatibility support for OSS (my own Linux partition, which runs the current version of Gentoo x86-64, does not, for example). While it is generally possible to install the OOS compatibility library, it doesn't change the fact that you're using an outdated system for your sound access.

LotusDream: You may want to start over learning the ALSA library, which if nothing else is a lot more complete than the OSS sound support.

On a related note, you are reading in and outputting raw sound data from the sound card. I'm not sure that the data you're collecting would work on other models of sound cards than the one you are using yourself. I may be mistaken about this, but in any case, you probably want to convert the sound data to a compressed format before sending it anywhere, as WAV sound data tends to be rather large.

This article has been dead for over six months. Start a new discussion instead.