Lista 2 de MD2

Questao 9

Desenvolver um código que calcule sistemas de congruência linear de até ### 4 equações utilizando o teorema chinês do resto (linguagens C ou C++)

#include <stdio.h>
#include <stdlib.h>

void limpaTerminal() {
#ifdef _WIN32
    system("cls");
#else
    system("clear");
#endif
}

int MDC(int num1, int num2){

    int aux;

    if(num1 % num2 == 0)
        return num2;
    else{
        aux = num2;
        num2 = num1 % num2;
        num1 = aux;
        return MDC(num1, num2);
    }

}

void imprimeMenu(){
    printf("***** Sistemas de congruencia pelo teorema chines do resto *****\n\n");
    printf("Resolve sistemas da forma ax = b mod n. \n\n");
}

int verificaQtdCongruencias(int qtdCongruencias){
    if(qtdCongruencias > 4 || qtdCongruencias < 1){
        printf("Qtd de congruencias invalido!\n");
        printf("Deve ser um valor entre 2 e 4. \n");
    }
    return 0;
}

int main(){

    int qtdCongruencias;

    imprimeMenu();

    printf("Digite quantas congruencias estao no sistema: ");
    scanf("%d", &qtdCongruencias);

    verificaQtdCongruencias(qtdCongruencias);

    int *a = (int*)malloc(qtdCongruencias * sizeof(int));
    int *b = (int*)malloc(qtdCongruencias * sizeof(int));
    int *n = (int*)malloc(qtdCongruencias * sizeof(int));
    int *M = (int*)malloc(qtdCongruencias * sizeof(int));
    int *X = (int*)malloc(qtdCongruencias * sizeof(int));

    for (int i = 0; i < qtdCongruencias; i++){
        limpaTerminal();
        printf("Nova Congruencia. \n\n");
        printf("Digite o valor a da congruencia: ");
        scanf("%d", &a[i]);
        printf("Digite o valor b da congruencia: ");
        scanf("%d", &b[i]);
        printf("Digite o valor n da congruencia: ");
        scanf("%d", &n[i]);
    }

    for (int i = 0; i < qtdCongruencias; i++){
        printf("%dx = %d mod %d \n", a[i], b[i], n[i]);
    }

    for (int i = 0; i < qtdCongruencias; i++){
        if(a[i] != 0){
            int inverso = 1;
            while((a[i]*inverso)%n[i] != 1){
                inverso++;
            }
            a[i] = 1;
            b[i] = (b[i]*inverso)%n[i];
        }
    }

    for(int i = 0; i < qtdCongruencias; i++){
        for(int j = i + 1; j < qtdCongruencias; j++){
            if(MDC(n[i], n[j]) != 1){
                printf("Nao e possivel resolver pelo teorema chines do resto. \n");
                    free(a);
                    free(b);
                    free(n);
                    free(M);
                    free(X);
                    return 0;
            }
        }
    }
        
    int N = 1;
    for(int i = 0; i < qtdCongruencias; i++){
        N *= n[i];
    }

    for(int i = 0; i < qtdCongruencias; i++){
        M[i] = N/n[i];
    }

    for (int i = 0; i < qtdCongruencias; i++){
        X[i] = 1;
        while((M[i]*X[i])%n[i] != 1){
            X[i]++;
        }
    }
        
        switch(qtdCongruencias){

            case 2: 
                printf("x = %d * %d * %d + %d * %d * %d mod %d \n", b[0], X[0], M[0], b[1], X[1], M[1], N);
                printf("x = %d + %d mod %d \n", b[0] * X[0] * M[0], b[1] * X[1] * M[1], N); 
                printf("x = %d mod %d \n", b[0] * X[0] * M[0] + b[1] * X[1] * M[1], N);
                printf("x = %d mod %d \n", (b[0] * X[0] * M[0] + b[1] * X[1] * M[1]) % N, N);
                break;

            case 3: 
                printf("x = %d * %d * %d + %d * %d * %d +  %d * %d * %d mod %d \n", b[0], X[0], M[0], b[1], X[1], M[1], b[2], X[2], M[2], N); 
                printf("x = %d + %d + %d mod %d \n", b[0] * X[0] * M[0], b[1] * X[1] * M[1], b[2] * X[2] * M[2], N);
                printf("x = %d mod %d \n", b[0] * X[0] * M[0] + b[1] * X[1] * M[1] + b[2] * X[2] * M[2], N);
                printf("x = %d mod %d \n", (b[0] * X[0] * M[0] + b[1] * X[1] * M[1] + b[2] * X[2] * M[2]) % N, N);
                break;

            case 4: 
                printf("x = %d * %d * %d + %d * %d * %d +  %d * %d * %d + %d * %d * %d mod %d \n", b[0], X[0], M[0], b[1], X[1], M[1], b[2], X[2], M[2], b[3], X[3], M[3], N); 
                printf("x = %d + %d + %d + %d mod %d \n", b[0] * X[0] * M[0], b[1] * X[1] * M[1], b[2] * X[2] * M[2], b[3] * X[3] * M[3], N);
                printf("x = %d mod %d \n", b[0] * X[0] * M[0] + b[1] * X[1] * M[1] + b[2] * X[2] * M[2] + b[3] * X[3] * M[3], N);
                printf("x = %d mod %d \n", (b[0] * X[0] * M[0] + b[1] * X[1] * M[1] + b[2] * X[2] * M[2] + b[3] * X[3] * M[3]) % N, N);
                break;

        }

    free(a);
    free(b);
    free(n);
    free(M);
    free(X);

    return 0;
}
}

Questao 10

Desenvolver um código que calcule a criptografia RSA, no qual o

usuário irá definir os primos (p e q) , número E e o tamanho do

bloco. Definir um pré-código com o alfabeto iniciando em A =11, como

mostrado em aula (linguagens C ou C++)

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

int MDC(int num1, int num2) {
    int aux;
    if (num1 % num2 == 0)
        return num2;
    else {
        aux = num2;
        num2 = num1 % num2;
        num1 = aux;
        return MDC(num1, num2);
    }
}

int inverso(int e, int z) {
    int inverso = 1;
    while ((e * inverso) % z != 1) {
        inverso++;
    }
    return inverso;
}

int mapearCaractere(char c) {
    if (c >= 'A' && c <= 'Z')
        return c - 'A' + 11;
    else if (c == ' ')
        return 99;
    else
        return -1;
}

void converterParaBlocos(char mensagem[], int tamBloco, int blocos[], int *qtdBlocos) {
    int i, num, pos = 0;
    char blocoAtual[256] = "";

    for (i = 0; mensagem[i] != '\0'; i++) {
        num = mapearCaractere(mensagem[i]);
        if (num == -1) {
            printf("Caractere inválido na mensagem: '%c'\n", mensagem[i]);
            continue;
        }

        char temp[10];
        sprintf(temp, "%d", num);
        strcat(blocoAtual, temp);

        if ((i + 1) % tamBloco == 0 || mensagem[i + 1] == '\0') {
            blocos[pos++] = atoi(blocoAtual);
            blocoAtual[0] = '\0';
        }
    }
    *qtdBlocos = pos;
}

int criptografar(int m, int e, int n) {
    long long resultado = 1;
    for (int i = 0; i < e; i++) {
        resultado = (resultado * m) % n;
    }
    return (int)resultado;
}

int descriptografar(int c, int d, int n) {
    long long resultado = 1;
    for (int i = 0; i < d; i++) {
        resultado = (resultado * c) % n;
    }
    return (int)resultado;
}

int main() {
    int p, q, e, tamBloco, blocos[256], qtdBlocos;
    char mensagem[256];

    printf("\nDigite um numero p primo: ");
    scanf("%d", &p);
    printf("\nDigite um numero q primo: ");
    scanf("%d", &q);

    int n = p * q;
    int z = (p - 1) * (q - 1);

    printf("\nDigite o valor de e: ");
    scanf("%d", &e);

    if (e > n || e > z || MDC(e, z) != 1) {
        printf("Valor de e invalido. \n");
        printf("e deve ser menor que n, menor que z e mdc(e, z) = 1");
        return 0;
    }

    printf("\nDigite o tamanho do bloco: ");
    scanf("%d", &tamBloco);

    int d = inverso(e, z);

    printf("\nDigite uma mensagem: ");
    scanf(" %[^\n]", mensagem);

    memset(blocos, 0, sizeof(blocos));
    converterParaBlocos(mensagem, tamBloco, blocos, &qtdBlocos);

    printf("\nBlocos gerados:\n");
    for (int i = 0; i < qtdBlocos; i++) {
        printf("Bloco %d: %d\n", i + 1, blocos[i]);
    }

    printf("\nBlocos criptografados:\n");
    int blocosCriptografados[256];
    for (int i = 0; i < qtdBlocos; i++) {
        blocosCriptografados[i] = criptografar(blocos[i], e, n);
        printf("Bloco %d: %d\n", i + 1, blocosCriptografados[i]);
    }

    printf("\nBlocos descriptografados:\n");
    for (int i = 0; i < qtdBlocos; i++) {
        int blocoOriginal = descriptografar(blocosCriptografados[i], d, n);
        printf("Bloco %d: %d\n", i + 1, blocoOriginal);
    }

    return 0;
}

##Questao 11

Desenvolver um código que calcule o CPF e o ISBN de um livro,

utilizando as regras de congruência (linguagens C ou C++)

codigo verificador de cpf

#include <stdio.h>
#include <string.h>

int verificaDigito10(char cpf[]){
    int verifica = 0;

    for(int i = 0; i < 9; i++){
        verifica += (cpf[i] - '0') * (10 - i);
    }

    int resto = verifica % 11;
    int digito10 = (resto < 2) ? 0 : (11 - resto);


    if(digito10 == (cpf[9] - '0')){
        return 1;
    }else{
        return 0;
    }

}

int verificaDigito11(char cpf[]){
    int verifica = 0;

    for(int i = 0; i < 10; i++){
        verifica += (cpf[i] - '0') * (11 - i);
    }

    int resto = verifica % 11;
    int digito11 = (resto < 2) ? 0 : (11 - resto);

    if(digito11 == (cpf[10] - '0')){
        return 1;
    }else{
        return 0;
    }

}

void verificaCPF(char cpf[]){
    if(verificaDigito10(cpf) == 1 && verificaDigito11(cpf) == 1){
        printf("\n CPF Valido \n");
    }else{
        printf("\n CPF Invalido \n");
    }
}

int main(){
    
    char cpf[12];

    printf("Insira um cpf (so numeros): ");
    scanf("%11s", cpf);

    verificaCPF(cpf);

}

codigo verificador de isbn

#include <stdio.h>
#include <string.h>

int verificaDigito10(char isbn[]){
    int verifica = 0;

    for(int i = 0; i < 9; i++){
        verifica += (isbn[i] - '0') * (10 - i);
    }

    int resto = verifica % 11;
    if(verifica == 10){
        if(isbn[9] == 'x'){
            return 1;
        }else{
            return 0;
        }
    }

    if (resto == (isbn[9] - '0')){
        return 1;
    }else{
        return 0;
    }

}

int main(){
    
    char isbn[10];

    printf("Insira um isbn (so numeros): ");
    scanf("%10s", isbn);

    if(verificaDigito10(isbn) == 1){
        printf("\n Isbn Valido \n");
    }else{
        printf("\n Isbn Invalido \n");
    }

}