Instituto Superior de Engenharia de Coimbra

Instituto Superior de Engenharia de Coimbra
Departamento de Informática e de Sistemas
2002 – 2003
Trabalho da cadeira de Análise Matemática II sobre:
Realizado Por:
• André Tenreiro de Almeida – 21120610
[email protected]
Índice
I . Abstract..................................................................................................3
1. Introdução ..............................................................................................3
1.1 Criptografia, Criptologia, CriptoAnálise, CriptoSistema ............3
2. Técnicas e Algoritmos de Criptologia e Criptoanálise ............................4
2.1 Criptografia Clássica ..................................................................4
2.1.1 Encriptação de César ...........................................................4
2.1.2 Algoritmo de Vigenére.........................................................6
2.2 Criptografia Moderna ou Convencional......................................8
3. Matemática e Criptologia .......................................................................9
3.1 Teorica dos Números................................................................10
3.1.1 Definições e grupos de interesse na Teoria dos Números ..........10
3.1.1.1 Números Amigáveis ...........................................10
3.1.1.2 Números Perfeitos..............................................10
3.1.1.3 Números Primos ................................................11
3.1.2 Aplicando os conceitos da Teoria dos Números na Criptografia ...........11
3.2 Análise Combinatória ...............................................................12
3.2.1 Aplicando a Teoria dos Grafos em Criptografia ......................12
3.2.2 Estatística na Criptografia ...................................................13
3.3 Geometria.................................................................................14
3.3.1 Aplicações de Curvas Elípticas em Criptografia ......................14
3.4 Fundamentos da Matemática ....................................................14
3.4.1 Complexidade de Algoritmos ..............................................15
4. Conclusões ...........................................................................................17
5. Bibliografia ..........................................................................................17
6. Contactos .............................................................................................17
7. Anexos .................................................................................................18
2
I. Abstract
Este trabalho pretende analisar algumas técnicas de Criptologia, como criar
algoritmos de encriptação e como quebrar a sua segurança usando Matemática.
1. Introdução
Hoje em dia com o crescimento exponencial dos meios de comunicação, como
telefones, telemóveis, faxes, Internet, cartas, satélites, etc. Permitem-nos comunicar
facilmente com alguém, mesmo a longa distancias. Contudo ao enviar informação
confidencial ou sensível, estamos sujeitos a que terceiros possam ler a nossa mensagem
que se destina apenas ao destinatário.
Por essas razões, informação confidencial deve ser tratada de modo diferente,
como por exemplo, encriptar a informação de modo que apenas o emissor e o receptor
possam tomar conhecimento do conteúdo mensagem enviada.
Ilustração 1 Esquema de comunicação
1.1
Criptologia, Criptografia, Criptoanálise, Criptosistema.
A arte e a ciência de manter a informação segura é a criptografia, e é praticada
por criptógrafos. Por sua vez a criptoanálise é a arte e a ciência de quebrar o código da
criptografia e é praticada por criptoanalistas. A ciência da matemática que acompanha a
criptografia e a criptoanálise é denominada de criptologia, e é praticada por criptólogos,
que tem um conhecimento profundo de matemática teórica. Um algoritmo de
encriptação e também de desencriptação é denominado de criptosistema.
3
2 Técnicas e Algoritmos de Criptologia e Criptoanálise
2.1
Criptografia Clássica
2.1.1 Encriptação de César
Rege na história actual que o famoso imperador de Roma, Júlio César, pretendia
enviar uma mensagem confidencial mas não confiava nos seus mensageiros. Então criou
uma forma de codificar a mensagem, substituído o carácter pretendido por 3 caracteres á
direita. Por exemplo, A é substituído por D, B por E, C por F, etc..
Encriptação de César
F G H I J K L M N O P Q R S
Alfabeto
A B C D E
Normal
Alfabeto
D E F G H I
Codificado
J
K L M N O P
Q R S T
T
U V W X Y Z
U V W X Y Z
Exemplo: Roma vai ser atacada
Codificado: URPD YDL VHU DWDFDGD
Este texto codificado (cifra) pode ser facilmente quebrado usando para tal efeito,
estatística matemática.
Recorrendo a conceitos matemáticos básicos:
Algoritmo:
Se atribuir-mos a cada letra o equivalente de um numero (a=1, b=2, c=3, etc..),
poderíamos criar um algoritmo em que p (Texto normal) substituída por C (cifra)
teríamos:
Encriptação:
Para o caso especifico da encriptação de César
C = E(P) = (p + 3) mod(26)
Para um caso geral do algoritmo de César:
C = E(p) = (p + k) mod(26) k ∈ N : 1 ≤ k ≤ 25, sendo o valor da permutação.
DesEncriptação:
p = D(C) = (C – k ) mod(26) k ∈ N : 1 ≤ k ≤ 25, sendo o valor da permutação.
4
A B C
Segurança do Algoritmo:
Este tipo de criptologia clássica, hoje em dia apenas servirá para um mero uso
amador e não para informação realmente confidencial. Aplicando o método de “Força
Bruta”, i.e, tentar todas as possibilidades até encontrar uma certa combinação que faça
sentido, teríamos 25 possibilidades para testar. Hoje em dia a capacidade dos
computador actuais com um programa informático destinado a esse fim, testar essas
possibilidades faria isso em fracções de segundo tornando o código ou algoritmo
trivialmente quebrável.
Quebrar o Algoritmo de César:
URPD
YDL
VHU
TQOC
SPNB
ROMA
QNLZ
PMKY
OLJX
NKIW
MJHV
LIGU
KHFT
J GES
IFDR
HECQ
GDBP
FCAO
EBZN
DAXM
CZYL
BYZK
AXWJ
ZWVI
YVUH
XUTG
WTSF
SSRE
XCK UGT
WBJ TFS
VAI SER
UZH RDQ
TYG QCP
SXF PBO
RWE OAN
QVD NZM
PUC MYL
OTB LXK
NSA KWJ
MZ
JVI
LRY IUH
KQX HTG
JPW GSF
IOV FRE
HNU EQD
GMT DPC
FLS
CO
EKR
BNA
DJQ
AMZ
CIPO ZLX
BHN YKY
AGM XJW
ZFL
WIV
DWDFDGD
Chave
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
CVCECFC
BUBDBEB
ATACADA
ZSZBZCZ
YTYAYBY
XSXZXAX
WRWYWZW
VQVXVYV
UPUWUXU
TOTVTWT
SNSUSVS
RMRTRUR
QLQSQTQ
PKPRPSSP
OJOQORO
NINPNQN
MHMOPM
LGLNLOL
KFKMKNK
JEJLJMJ
IDIKINI
HCHJHLH
GBGIGKG
FAFGFJF
RZRFRIR
Como podemos constatar, a 3ª chave ou possibilidade faz sentido. O Algoritmo
de encriptação de César tem um tamanho de chave de cerca de 32 bits, que é facilmente
quebrável e inseguro. Contudo para quebrar a segurança deste algoritmo e permitir o
uso da criptoanálise através de “Força Bruta” precisamos de saber importantes
características:
• Ter conhecimento do algoritmo de encriptação e desencriptação
• Apenas temos de testar 25 chaves
• Conhecer a linguagem do texto descodificado
5
2.1.2 Algoritmo de Vigenére
Com apenas 25 possibilidades, o algoritmo de César está longe de ser um
criptosistema seguro. Com intuito de aumentar a fiabilidade do criptosistema, Vigenére
criou uma forma alternativa de codificação:
Exemplo: A = ERX ; B = 34 ; C=A; etc..
Aumentando o número de possibilidades usando a “Força Bruta” para atacar a cifra,
recorremos a uma maneira matemática de estudar a cifra e quebra-la. Eis um exemplo:
O centro de operações de criptologia Americano, National Security Agency (NSA),
destinado a espionagem electrónica intercepta uma mensagem codificada destinada a
um centro de operações Russo. A seguinte mensagem captada lia-se:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
Recorrendo a uma simples estatística matemática para contar a frequência dos
caracteres em texto codificado temos:
P
Z
S
U
O
M
13.33
11.67
8.33
8.33
7.50
6.67
H
D
E
V
X
Frequência dos caracteres na cifra (%)
5.83
F
3.33
B
1.67
5.00
W
3.33
G
1.67
5.00
Q
2.50
Y
1.67
4.17
T
2.50
I
0.83
4.17
A
1.67
J
0.83
C
K
L
N
R
0.00
0.00
0.00
0.00
0.00
Sabendo que o texto codificado está na língua inglesa, vamos analisar a frequência dos
caracteres da língua inglesa, sendo a língua mais standardizada, comparando-os com a
frequência dos caracteres da cifra.
6
Ling. Inglesa
Cifra
14
12
10
8
6
4
2
0
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Ilustração 2 Frequência dos caracteres na língua inglesa e na nossa cifra
Recordando a cifra
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
Recorrendo a Substituição dos caracteres mais frequentes da língua inglesa pelos
caracteres mais frequentes da cifra:
UZQSOVUOHXMOPVGPOZPEVSGZWSZOPFPESXUDBMETSXAIZ
t a
e e te
a that
e e a
a
VUEPHZHMDZSHZOWSFPAPPDTSVPQUZWYMXUZUHSX
e t
ta t há e ee
a e
th
t
a
EPYEPOPDZSZUFPOMBZWPFUPZHMDJUDTMOHMQ
e e e tat
e
the
t
Continuando o processo, como se fosse um “puzzle” ou uma sopa de letras
conseguimos chegar ao texto descodificado:
it will disclosed yesterday that several informal but
direct contacts have been made with political
representatives of the viet cong in moscow
7
Segurança do Algoritmo
Cifras monoalfabéticas são facilmente quebráveis porque refletem-se em estatísticas de
frequência dos caracteres do alfabeto em que foram escritas.
Mais segura do que o Algoritmo de César, embora também se considera esta cifra
meramente para uso amador e trivial.
2.2 Criptografia Moderna ou Convencional
A cada dia que passa são criados novos criptosistemas, descobrem-se novas
técnicas matemáticas e com o avanço da tecnologia, criam-se novos computadores
capazes de processar largas quantidades de informação em cada vez menos tempo.
Hoje em dia a criptografia clássica não oferece a segurança necessária para
corporações e pessoas que tenham de manter informação confidencial. A pensar nisso
NSA (National Security Agency) dos EUA, criou uma equipa de matemáticos
destinados a desenvolver novos algoritmos de encriptação “inquebráveis”, bem como
outras centrais de inteligência mundiais e universidades.
DES
O criptosistemas DES (Data Encryption System), desenvolvido na década de
1977 pelo NIST (National Institute of Standards and Technology) basea-se em trocas
sucessivas dos caracteres de forma a ser extremamente difícil seguir o rasto, ao
contrário da criptografia clássica.
Baseando-se numa chave de 56-bits, i.e, teríamos 256 possibilidades para testar
até quebrar o código! Se não parece ser muito, pense que no planeta terra existem cerca
de 2170 átomos! Isto num computador actual poderia demorar décadas ou mesmo
centenas de anos.
IDEA
O Algoritmo IDEA de encriptação, elaborado por Xuejia Lai e James Massey
em 1992. Baseado de fundamentos matemáticos bem sólidos e complexos, o algoritmo
IDEA , sendo o algoritmo também duas vezes mais rápido que o DES. Tendo 2128
possibilidades para um ataque de “força-bruta” até quebrar ó código, faz-nos crer que é
considerado um dos mais seguros, e um ataque de “força bruta” a uns anos atrás num
mero computador da época poderia demorar até 1013 anos, ao comprar com a idade do
universo, cerca de1010 anos, faz-nos crer que realmente é muito tempo!
8
RSA
Sem dúvida um dos algoritmos mais usados actual, tem a caracteristica de ser
de“Chave-Publica”, ou seja, temos uma chave publica e uma chave privada. A Chave
publica é conhecida e pode ser partilhada, mas a chave privada tem de ser mantida em
segredo. Este método aumenta bastante a segurança do algoritmo podendo este chegar a
ter uma chave de 1024-bits, i.e, 21024 possibilidades de desEncriptação, para ter uma
maior noção destas grandezas, o volume do universo é cerca de 2280 cm³!
Este algoritmo é cerca de 1000 vezes mais lento que o DES, mas sem dúvida
bem mais seguro. Para gerar uma chave publica, o algoritmo usa pura Matemática,
Teoria dos Números, como iremos abordar mais á frente, vejamos os passos para
criação de uma chave:
1. Gere dois números grandes de forma aleatória (e distintos) primos p e q, e os dois do
mesmo tamanho.
2. Gere n, tal que: n = pq e φ = (p - 1)(q - 1).
3. Gere um inteiro aleatório, E, 1 < E < φ, tal que MMC(E, φ) = 1
4. Usa-se o algoritmo Euclidiano para gerar um unico inteiro, d
1 < d < φ, tal que Ed = 1 (mod φ).
5. A chave publica é (n, E); e a Chave privada é d.
NOTA: Os Algoritmos utilizados encontram-se em Anexo.
3 Matemática e a Criptologia
A Matemática é a ciência que investiga as relações entre entidades definidas
abstrata e logicamente, ou ainda, o ciência que tem por objecto o estudo da grandeza
mensurável e calculável. Para que os estudos dessa ciência possam avançar, a ciência
Matemática é particionada em diversas divisões principais, a saber:
• Fundamentos da Matemática
• Álgebra
• Análise Combinatória
• Análise Matemática
• Geometria
• Teoria dos Números
• Topologia
Todas estas diferentes áreas de matemática tem o uso na criptografia, ajudando-a a
tornar-se cada vez mais complexa.
9
Ilustração 3 Areas de Matemática aplicadas em Criptografia
3.1 Teoria dos Números
Para o presente estudo, a Teoria Elementar dos Números contém diversos itens
de interesse, destacando-se a divisibilidade, primalidade, máximo divisor comum,
congruências e resíduos – associados às operações modulares. Esse conjunto de itens é
comumente conhecido como "teoria multiplicativa do anel Z de números inteiros".
3.1.1 Definições e grupos de interesse na Teoria dos Números
3.1.1.1 Números Amigáveis
Também encontrados na literatura como "números amigos", são pares de
Números onde cada um é igual à soma dos divisores do outro. Os árabes, em especial,
desenvolveram diversos algoritmos para a determinação de números amigáveis. O
quadro a seguir apresenta alguns desses números.
Números Amigos
220 e 284
Números
220
284
Factores
1,2,4,5,10,11,20,22,44,55,110
1,2,4,71,142
Ilustração 4 Exemplo de dois números amigos
Observa-se, no quadro acima, que a soma de todos os factores de 220 resulta em 284;
por sua vez, a soma dos factores de 284 resulta em 220. Não foram encontrados Muitos
números amigos: 1184 e 1210; 2620 e 2924; 5020 e 5564; e 6232 e 6368.
Recentemente, os matemáticos extenderam essa ideia para cadeia de números
amigáveis, sendo a soma dos factores do último da cadeia, o valor do primeiro.
3.1.1.2 Números Perfeitos
Os chamados números perfeitos são números cuja soma de seus factores resulta
no valor do próprio número. Por exemplo, seis é um número perfeito, visto que a soma
10
de seus factores - 1, 2 e 3 - resulta em 6. Euclides propôs - e pode-se expressar em um
formalismo dos dias actuais - que um número N da forma (2n - 1)* 2(n-1) é um número
perfeito, se o factor (2n - 1) 10 for um número primo. Assim, para n = 2, 3, 5 ou 7, a
expressão (2n - 1) assume os valores 3, 7, 31 ou 127 - os quais são também primos. Para
esses valores, podem-se obter o números perfeitos 6, 28, 496 e 8128. O estudo de
números perfeitos levou Fermat a estudos que possibilitaram base a seu teorema, e serve
de base para o estudo das fracções continuadas – uma das tendências Matemáticas para
Criptografia.
3.1.1.3 Números Primos
São números cujos factores são apenas um e o próprio número, ou seja, não têm
outros divisores. Tendo uma infinita possibilidade de números primos, sendo esse
factor, a restrita divisibilidade, e sua infinitude que detêm características que garantem
interessantes propriedades a determinados algoritmos aplicados a Criptografia.
Há apenas uma forma de determinar se um número é ou não primo: aplicando
um teste de primalidade. E, para isso, despende-se considerável tempo, mesmo
utilizando-se de grandes recursos computacionais. Baseado nessa dificuldade, repousa
a segurança da actual Criptografia.
Algoritmo de Verificação de um Numero Primo
Inicialização: Ler p
Primo := Verdadeiro
Iteração: r := (2 p/2- 1)/2*p
Para i := 1 até r faça
M(p) MOD Éprimo(r) = 0 então Primo := False
Término: Se Primo então imprimir "M(p) é Primo"
Senão imprimir "M(p) não é primo"
Saída: Mensagem de status: ou M(p) é primo, ou não é.
NOTA: A respectiva adaptação em Linguagem de programação C, encontra-se em
anexo.
3.1.2 Aplicando os conceitos da Teoria dos Números na Criptografia
Em 1977, foi apresentado um criptosistema de chave pública: o RSA, assim
chamado por ser a abreviatura dos sobrenomes de seus autores - Rivest, Shamir e
Adleman. Esse criptosistema é baseado no facto de que é muito mais fácil multiplicar
dois números primos grandes, do que a factoração do produto resultante desses primos
grandes, sendo baseado no teorema de Euler.
11
3.2 Análise Combinatória
A Análise Combinatória está subdividida em Teoria dos Grafos, Arranjos e
Configurações Combinatórias, Probabilidade, Estatística Matemática, Métodos de
Inferência, Matemática Computacional, Métodos Numéricos, Interpolação, Cibernética
Matemática, Teoria dos Sistemas de Controle, Teoria da Informação, Semiótica e
Pesquisa Operacional. A figura a seguir ilustra parte da contribuição de interesse para a
Criptografia.
Ilustração 5 Contribuições da Análise Combinatória para a Criptografia.
A subdivisão de interesse para a Criptografia é a Teoria dos Grafos – com a
contribuição significativa para a Criptografia de blocos -, conforme ver-se-á a seguir.
Contudo, a Estatística e a Probabilidade têm também aplicação, vista a importância dos
primeiros métodos de Criptoanálise.
3.2.1 Aplicando a Teoria dos Grafos em Criptografia
Sem a menor dúvida, a maior contribuição da Teoria dos Grafos para a
Criptografia foi o estudo dos circuitos, aplicando-se no Data Encryption Standard DES - adaptação do NIST para o algoritmo Lucifer da IBM, em 1977. Esse padrão é
orientado a blocos, ou seja, divide a mensagem ou o texto a ser criptografado em grupos
de 64 bits. Utilizando-se uma chave de 56 bits, de duas tabelas para transposição inicial e final – e uma técnica de cifragem – repetida 16 vezes, efetuavam a criptografia
de forma relativamente segura. A figura a seguir apresenta o esquema genérico do
funcionamento do DES, em blocos.
12
Ilustração 6 Esquema de funcionamento do DES.
3.2.2 Estatística na Criptografia
Como podemos ver no Capitulo 2, nas técnicas de Encriptação Clássica, através
das quais recorremos ás cifras mais frequentes para descobrir a respectiva combinação.
Ilustração 7 Frequência dos caracteres na língua Portuguesa.
NOTA: Em Anexo está um programa em C para contabilizar a frequência dos caracteres
num texto.
13
3.3 Geometria
As principais subdivisões da Geometria são a Geometria Geral, as Geometrias
Euclidiana e pseudo-Euclidiana, a Geometria Analítica, a Geometria projectiva, a
Trigonometria, os Conjuntos convexos, a Geometria Descritiva, a Geometria
Diferencial e a Geometria das Curvas Elípticas.
Ilustração 8 Contribuição da Geometria para o estudo da Criptografia.
Sucintamente, explicamos as aplicações das Curvas Elípticas, sendo essas as mais
importantes da área de Geometria na Criptografia.
3.3.1 Aplicações de Curvas Elípticas em Criptografia
•
•
Esquemas Troca de Chaves criptográficas
Algoritmo RSA
3.4 Fundamentos da Matemática
As principais subdivisões dos Fundamentos da Matemática são a Lógica
Matemática, Formalismo, o Positivismo, a Semântica, a Inferência, a Complexidade e
a Teoria dos Conjuntos . Para aplicações em Criptografia, é relevante a compreensão da
Complexidade.
14
Ilustração 9 Contribuição dos Fundamentos da Matemática para o estudo da Criptografia
3.4.1 Complexidade de Algoritmos
A complexidade computacional de técnicas ou algoritmos criptográficos pode
ser melhor analisado pela teoria da complexidade. Tipicamente, as afirmações da Teoria
dos Números garantem que todos os algoritmos criptográficos podem ser quebrados.
Assim, torna-se de interesse qualquer estudo que preveja o esforço necessário para
efectuar a quebra dos algoritmos que se enquadrem em algum tipo de problema - em
algum conjunto ou classe de problemas.
Para os estudos de classes de complexidade de problemas, normalmente empregam-se
os problemas de Decisão, visto a maior simplicidade entre os problemas associados.
Com relação à representação, emprega-se em geral o termo O. Dado um algoritmo e o
tamanho de sua entrada - n -, diz-se que a complexidade é:
• Linear - se o tempo para sua execução é O(n);
• Polinomial - se o tempo para a sua execução é O(nt), para algum t constante;
• Exponencial - se o tempo para a sua execução é O(th(n)), para alguma constante t, e um
polinómio h(n).
15
Como se poderia calcular a complexidade de determinado algoritmo? Através do
número de operações. Pode-se verificar o número de iterações de seus laços, por
exemplo; no caso das repetições condicionais, pode-se avaliar o pior caso - ou seja,
quando ocorre o maior número de repetições. Nos casos de decisões, assume-se o pior
caso. Há autores que buscam utilizar-se dos casos médios - ou seja, considerando-se a
média entre o número de ocorrências do pior caso, e do melhor caso.
Algoritmo Exemplo;
n, i, j: integer; x, Poli: real;
A, S: array [0..100] of real;
BEGIN
Read(x,n);
For i:= 0 to n do
Begin
S[i] := 1; Read (a[i);
For j := 1 to i do S[i] := x * S[i];
S[i] := A[i] * S[i];
End; {for}
Poli := 0;
For i := 0 to n do Poli := Poli + S[i];
Write ('O valor em ',x,' é: ', Poli);
END;
16
4. Considerações Finais
Sem dúvida que o papel da Matemática é fundamental para o desenvolvimento e
análise da Criptografia, como já vimos. Com o auxilio dos computadores, que cada dia
se tornam mais potentes, podemos criar e quebrar CriptoSistemas cada vez mais
complexos, e com o desenvolvimento rápido das novas tecnologias e o aumento da
preocupação do direito à privacidade, faz com que esta Área, a Criptologia nunca pare
de crescer.
5. Bibliografia
•
Applied Cryptography, Bruce Schneier.
o Cota Biblioteca ISEC: 1A 16 3
•
Cryptography and Network Security, WilliamStallings
o Cota Biblioteca ISEC: 1A 16 1
•
Um Estudo sobre a Matemática empregada em Criptografia, Vinicius Gadis
Ribeiro
6. Contacto
André Tenreiro de Almeida
Numero Interno: 21120610
Regime: Misto
Email: [email protected]
17
7. Anexo
Nesta secção encontram-se programas em C e Algoritmos Matemáticos usados para a
criação e análise Criptológica.
Progama em C para Calcular a Frequencia dos Caracteres num texto :
/* Instituto Superior de Engenharia de Coimbra
Departamento de Engeharia Informatica e de Sistemas
Analise Matematica II
Trabalho de Criptografia
Andre Mendonca Tenreiro de Almeida
NI: 21120610
01/06/03
*/
#include <stdio.h>
#include <stdlib.h>
struct data {
int total;
int A, B, C,
N, O, P,
int a, b, c,
n, o, p,
int numb;
int others;
D,
Q,
d,
q,
E,
R,
e,
r,
F,
S,
f,
s,
G,
T,
g,
t,
H,
U,
h,
u,
I,
V,
i,
v,
J,
W,
j,
w,
K,
X,
k,
x,
L,
Y,
l,
y,
M,
Z;
m,
z;
} var;
int main(int argc, char **argv) {
FILE *fp, *fp2;
char *filename, *filename2;
char chr;
float f_A, f_B, f_C, f_D,
f_N, f_O, f_P, f_Q,
f_a, f_b, f_c, f_d,
f_n, f_o, f_p, f_q,
f_numb, f_others;
f_E,
f_R,
f_e,
f_r,
f_F,
f_S,
f_f,
f_s,
f_G,
f_T,
f_g,
f_t,
f_H,
f_U,
f_h,
f_u,
f_I,
f_V,
f_i,
f_v,
f_J,
f_W,
f_j,
f_w,
f_K,
f_X,
f_k,
f_x,
f_L,
f_Y,
f_l,
f_y,
f_M,
f_Z,
f_m,
f_z,
if (argc != 3) {
printf("\n\n");
printf("++++++++++++++++++++++++++++++++++++++++\n");
printf("++
Analise Matematica II
++\n");
printf("++++++++++++++++++++++++++++++++++++++++\n");
printf("+ Contador para Criptografia Classica ++\n");
printf("++++++++++++++++++++++++++++++++++++++++\n\n");
printf("usagem: %s input.txt output.txt\n\n", argv[0]);
exit(1);
}
18
filename = argv[1];
filename2 = argv[2];
fp = fopen(filename, "r");
if (fp == NULL) {
printf("ERRO: Ficheiro inexistente \"%s\".\n", filename);
exit(1);
}
fp2 = fopen(filename2, "w");
if (fp2 == NULL) {
printf("ERRO: Ficheiro inexistente \"%s\".\n", filename2);
exit(1);
}
printf("Espere...");
while(fread(&chr, 1, 1, fp) != 0) {
if (chr == ' ') {
/* null, nao faz nada */
}
if (chr == 'a') {
var.total++;
var.a++;
}
if (chr == 'b') {
var.total++;
var.b++;
}
if (chr == 'c') {
var.total++;
var.c++;
}
if (chr == 'd') {
var.total++;
var.d++;
}
if (chr == 'e') {
var.total++;
var.e++;
}
if (chr == 'f') {
var.total++;
var.f++;
}
if (chr == 'g') {
var.total++;
var.g++;
}
if (chr == 'h') {
19
var.total++;
var.h++;
}
if (chr == 'i') {
var.total++;
var.i++;
}
if (chr == 'j') {
var.total++;
var.j++;
}
if (chr == 'k') {
var.total++;
var.k++;
}
if (chr == 'l') {
var.total++;
var.l++;
}
if (chr == 'm') {
var.total++;
var.m++;
}
if (chr == 'n') {
var.total++;
var.n++;
}
if (chr == 'o') {
var.total++;
var.o++;
}
if (chr == 'p') {
var.total++;
var.p++;
}
if (chr == 'q') {
var.total++;
var.q++;
}
if (chr == 'r') {
var.total++;
var.r++;
}
if (chr == 's') {
var.total++;
var.s++;
}
if (chr == 't') {
var.total++;
20
var.t++;
}
if (chr == 'u') {
var.total++;
var.u++;
}
if (chr == 'v') {
var.total++;
var.v++;
}
if (chr == 'w') {
var.total++;
var.w++;
}
if (chr == 'x') {
var.total++;
var.x++;
}
if (chr == 'y') {
var.total++;
var.y++;
}
if (chr == 'z') {
var.total++;
var.z++;
}
if (chr == 'A') {
var.total++;
var.A++;
}
if (chr == 'B') {
var.total++;
var.B++;
}
if (chr == 'C') {
var.total++;
var.C++;
}
if (chr == 'D') {
var.total++;
var.D++;
}
if (chr == 'E') {
var.total++;
var.E++;
}
if (chr == 'F') {
var.total++;
var.F++;
21
}
if (chr == 'G') {
var.total++;
var.G++;
}
if (chr == 'H') {
var.total++;
var.H++;
}
if (chr == 'I') {
var.total++;
var.I++;
}
if (chr == 'J') {
var.total++;
var.J++;
}
if (chr == 'K') {
var.total++;
var.K++;
}
if (chr == 'L') {
var.total++;
var.L++;
}
if (chr == 'M') {
var.total++;
var.M++;
}
if (chr == 'N') {
var.total++;
var.N++;
}
if (chr == 'O') {
var.total++;
var.O++;
}
if (chr == 'P') {
var.total++;
var.Q++;
}
if (chr == 'Q') {
var.total++;
var.Q++;
}
if (chr == 'R') {
var.total++;
var.R++;
}
22
if (chr == 'S') {
var.total++;
var.S++;
}
if (chr == 'T') {
var.total++;
var.T++;
}
if (chr == 'U') {
var.total++;
var.U++;
}
if (chr == 'V') {
var.total++;
var.V++;
}
if (chr == 'W') {
var.total++;
var.W++;
}
if (chr == 'X') {
var.total++;
var.X++;
}
if (chr == 'Y') {
var.total++;
var.Y++;
}
if (chr == 'Z') {
var.total++;
var.Z++;
}
/* teste de condicao de numeros*/
if (chr >= '0' || chr <= '9') {
var.total++;
var.numb++;
}
/* teste de condicoes nao alfanumericos */
else {
var.total++;
var.others++;
}
} /* end of while */
printf("done!\n\n");
f_a = (float)(var.a * 100) / var.total;
f_A = (float)(var.A * 100) / var.total;
f_b = (float)(var.b * 100) / var.total;
23
f_B = (float)(var.B * 100) / var.total;
f_c = (float)(var.c * 100) / var.total;
f_C = (float)(var.C * 100) / var.total;
f_d = (float)(var.d * 100) / var.total;
f_D = (float)(var.D * 100) / var.total;
f_e = (float)(var.e * 100) / var.total;
f_E = (float)(var.E * 100) / var.total;
f_f = (float)(var.g * 100) / var.total;
f_F = (float)(var.G * 100) / var.total;
f_g = (float)(var.g * 100) / var.total;
f_G = (float)(var.G * 100) / var.total;
f_h = (float)(var.h * 100) / var.total;
f_H = (float)(var.H * 100) / var.total;
f_i = (float)(var.i * 100) / var.total;
f_I = (float)(var.I * 100) / var.total;
f_j = (float)(var.j * 100) / var.total;
f_J = (float)(var.J * 100) / var.total;
f_k = (float)(var.k * 100) / var.total;
f_K = (float)(var.K * 100) / var.total;
f_l = (float)(var.l * 100) / var.total;
f_L = (float)(var.L * 100) / var.total;
f_m = (float)(var.m * 100) / var.total;
f_M = (float)(var.M * 100) / var.total;
f_n = (float)(var.n * 100) / var.total;
f_N = (float)(var.N * 100) / var.total;
f_o = (float)(var.o * 100) / var.total;
f_O = (float)(var.O * 100) / var.total;
f_p = (float)(var.p * 100) / var.total;
f_P = (float)(var.P * 100) / var.total;
f_q = (float)(var.q * 100) / var.total;
f_Q = (float)(var.Q * 100) / var.total;
f_r = (float)(var.r * 100) / var.total;
f_R = (float)(var.R * 100) / var.total;
f_s = (float)(var.s * 100) / var.total;
f_S = (float)(var.S * 100) / var.total;
f_t = (float)(var.t * 100) / var.total;
f_T = (float)(var.T * 100) / var.total;
f_u = (float)(var.u * 100) / var.total;
f_U = (float)(var.U * 100) / var.total;
f_v = (float)(var.v * 100) / var.total;
f_V = (float)(var.V * 100) / var.total;
f_w = (float)(var.w * 100) / var.total;
f_W = (float)(var.W * 100) / var.total;
f_x = (float)(var.x * 100) / var.total;
f_X = (float)(var.X * 100) / var.total;
f_y = (float)(var.y * 100) / var.total;
f_Y = (float)(var.Y * 100) / var.total;
f_z = (float)(var.z * 100) / var.total;
f_Z = (float)(var.Z * 100) / var.total;
f_numb = (float)(var.numb * 100) / var.total;
f_others = (float)(var.others * 100) / var.total;
fprintf(fp2, "++++++++++++++++++++++++++++++++++++++++++\n");
fprintf(fp2, "+
Analise Matematica II
++\n");
fprintf(fp2, "++++++++++++++++++++++++++++++++++++++++++\n");
fprintf(fp2, "+ Contador para criptografia classica ++\n");
fprintf(fp2, "++++++++++++++++++++++++++++++++++++++++++\n\n");
fprintf(fp2, "Input file: %s
data: %s
hora: %s\n", filename,
__DATE__, __TIME__);
fprintf(fp2, "\n\n");
24
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
fprintf(fp2,
"Caracts Totais: %d \n\n", var.total);
"Charcts Totais:
Percentagem\n\n");
"A:%8d %16.2f\n", var.A, f_A);
"a:%8d %16.2f\n", var.a, f_a);
"B:%8d %16.2f\n", var.B, f_b);
"b:%8d %16.2f\n", var.b, f_B);
"C:%8d %16.2f\n", var.C, f_C);
"c:%8d %16.2f\n", var.c, f_c);
"D:%8d %16.2f\n", var.D, f_D);
"d:%8d %16.2f\n", var.d, f_d);
"E:%8d %16.2f\n", var.E, f_E);
"e:%8d %16.2f\n", var.e, f_e);
"F:%8d %16.2f\n", var.F, f_F);
"f:%8d %16.2f\n", var.f, f_f);
"G:%8d %16.2f\n", var.G, f_G);
"g:%8d %16.2f\n", var.g, f_g);
"H:%8d %16.2f\n", var.H, f_H);
"h:%8d %16.2f\n", var.h, f_h);
"I:%8d %16.2f\n", var.I, f_I);
"i:%8d %16.2f\n", var.i, f_i);
"J:%8d %16.2f\n", var.J, f_J);
"j:%8d %16.2f\n", var.j, f_j);
"K:%8d %16.2f\n", var.K, f_K);
"k:%8d %16.2f\n", var.k, f_k);
"L:%8d %16.2f\n", var.L, f_L);
"l:%8d %16.2f\n", var.l, f_l);
"M:%8d %16.2f\n", var.M, f_M);
"m:%8d %16.2f\n", var.m, f_m);
"N:%8d %16.2f\n", var.N, f_N);
"n:%8d %16.2f\n", var.n, f_n);
"O:%8d %16.2f\n", var.O, f_O);
"o:%8d %16.2f\n", var.o, f_o);
"P:%8d %16.2f\n", var.P, f_P);
"p:%8d %16.2f\n", var.p, f_p);
"Q:%8d %16.2f\n", var.Q, f_Q);
"q:%8d %16.2f\n", var.q, f_q);
"R:%8d %16.2f\n", var.R, f_R);
"r:%8d %16.2f\n", var.r, f_r);
"S:%8d %16.2f\n", var.S, f_S);
"s:%8d %16.2f\n", var.s, f_s);
"T:%8d %16.2f\n", var.T, f_T);
"t:%8d %16.2f\n", var.t, f_t);
"U:%8d %16.2f\n", var.U, f_U);
"u:%8d %16.2f\n", var.u, f_u);
"V:%8d %16.2f\n", var.V, f_V);
"v:%8d %16.2f\n", var.v, f_v);
"W:%8d %16.2f\n", var.W, f_W);
"w:%8d %16.2f\n", var.w, f_w);
"X:%8d %16.2f\n", var.X, f_X);
"x:%8d %16.2f\n", var.x, f_x);
"Y:%8d %16.2f\n", var.Y, f_Y);
"y:%8d %16.2f\n", var.y, f_y);
"Z:%8d %16.2f\n", var.Z, f_Z);
"z:%8d %16.2f\n", var.z, f_z);
"Numeros:%8d %16.2f\n", var.numb, f_numb);
"Outros:%8d %16.2f\n", var.others, f_others);
"\n");
fclose(fp); fclose(fp2);
} /* end of main() function */
25
PseudoCódigo para Calcular MMC:
INICIO FUNCAO MMC
RECEBE (den1, den2)
SE den1 < den2
INICIO
Mmc <- den1 – 1
FIM
SENAO
INICIO
Mmc <- den2 -1
FIM SE
FAZER
INICIO
Mmc <- den1 + 1
Resto <- (mmc % den1) + (mmc % den2)
FIM
ENQUANTO resto > 0
INICIO “Fracções”
OBTEM (num1, den1)
OBTEM (num2, den2)
Mmc <- CHAMA mmc(den1, den2)
num <- num1 * (mmc / den1)
num <- num + num2 * (mmc / den2)
MOSTRA (num, mmc)
FIM “Fracções”
Calculo do MMC em C:
#include <stdio.h>
int MMC(en1, int den2) {
int mmc, resto;
if (den1 < den2) {
mmc = den1 - 1;
}
else {
mmc = den2 -1;
}
do {
mmc = mmc + 1
resto=(mmc%den1)+(mmc%den2);
}
while (resto > 0);
return mmc;
}
int main(void) {
int num1, den1
int num2, den2;
26
int mmc, resto;
scanf(“%d %d”, &num1, &den1);
scanf(“%d %d”, &num2, &den2);
mmc = MMC(den1, den2);
num = num1 * (mmc / den1);
num += num2 * (mmc / den2);
printf(“%d /%d”, num, mmc);
return 1;
}
Algoritmo Euclidiano
Inicialização: r := 0
Interação: aplica-se o algoritmo de divisão de a por b, obtendo-se o resto r1 ;
se r1 ψ 0, divide-se b por r1, obtendo-se o resto r2;
se r2 ψ 0, divide-se r3 por r2, obtendo-se o resto r3.
Término: quando terminar o algoritmo de divisão
O MDC será o último rn ψ 0.
Algoritmo dos Números Primos
Inicialização: Ler p
Primo := Verdadeiro
Iteração: r := (2 p/2- 1)/2*p
Para i := 1 até r faça
Se M(p) MOD Éprimo(r) = 0 então Primo := False
Término: Se Primo então imprimir "M(p) é Primo"
Senão imprimir "M(p) não é primo"
Saída: Mensagem de status: ou M(p) é primo, ou não é.
Algoritmo de Euler, Caminho Euleriano
Inicialização: total := 0
i := 1
Iteração: Enquanto (total χ 2) e (i χ n) faça
grau := 0
Para j := 1 to n faça
grau := grau + M[i,j]
se impar(grau) então
total := total + 1
i := i + 1
Término: Se total > 2 então imprimir “não existe caminho Euleriano”
Senão imprimir “existe caminho Euleriano”
27