Enunciado do EP2

Enunciado do EP2

por Julian Monteiro -
Número de respostas: 70
Olá pessoal,

O Enunciado do segundo trabalho (EP2) já está no ar no Paca (http://paca.ime.usp.br/)
A data de entrega é 16 de Maio.

[]s
Julian
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por Gabriel Pugliese -

Bom, abri o .pdf e vi que nao tava escrito o nome do Goldman e vi tambem que estava escrito Ciclo Basico...

Pra BCC sera o mesmo ou nao ?

Em resposta à Gabriel Pugliese

Re: Enunciado do EP2

por Régis Diniz -
Acho que não. exitem dois arquivos de EP2: BCC e Ciclo Básico. Tem certeza de que vc escolheu o certo?
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por Rafael Franco -
Bem Julian, como o enunciado saiu com uma semana de atraso, deveria haver uma alteração no prazo de entrega também, não?
Em resposta à Rafael Franco

Re: Enunciado do EP2

por Julian Monteiro -
Ola Rafael,
Converse com os professores sobre a data entrega. Mas a priori eh dia 16 de Maio mesmo.
Afinal, depois desse vcs ainda terao mais um trabalho sorriso
Um abraco,
Julian
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por Alfredo Goldman -
Oi,
  Concordo com o Julian, apesar do EP ter sido divulgado com um pouco de
atraso, a data de entrega não foi alterada. Acho interessante que vocês (alunos)
comecem a fazer o EP o quanto antes...

Alfredo
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por César Machado -
Começando com a série de duvidas sobre o que fazer:

Eu posso usar um método da classe DecriptoRSA na classe CriptoRSA? Afinal elas vão ficar sempre juntas no mesmo arquivo... (o método potenciaModulo, por exemplo, que vai ser usado nas duas...)

Em resposta à César Machado

Re: Enunciado do EP2

por Julian Monteiro -
Cada classe deve funcionar independente da outra, por hora copie o método.
(Mais pra frente vcs vão aprender uma maneira elegante de solucionar essa redundância)

[]s
Julian
Em resposta à Julian Monteiro

Problema int/long para 'p' e 'q' - EP2

por Renato Bettiol -

Estou desenvolvendo o programa pedido e acho que tem um erro no enunciado: os valores para 'p' e 'q', primos do tipo 'long' gerados aleatoriamente, menores que 'tamanhoMax' devem calculados através de java.util.Random com nextInt(tamanhoMax), mas assim ele estará atribuindo valores do tipo 'int' para variáveis que são 'long'.

Ou 'p' e 'q' devem ser 'int' (acho que foi a intenção ao criar a proposta de exercício), assim como outros método que dependem desses valores, ou o método randômico para calculá-los deve usar 'nextLong' (afinal o Math.random está proibido), mas 'nextLong' atribui valores 'long' randomicos muito maiores que 512, em módulo. Como proceder?

Em resposta à Julian Monteiro

Dúvida

por Diogo José -
Como faço para carregar n e e na classe CriptoRSA, sendo que n e e foi gerado na classe DecriptoRSA?

Outra pergunta: Posso criar métodos adicionais?

Atenciosamente,

Diogo José
Em resposta à Diogo José

Re: Dúvida

por César Machado -
Existe um método na classe CriptoRSA chamado carregaChavePublica (long n, long e) que serve pra isso.

Sobre os métodos adicionais, acho que pode, sim.
Em resposta à César Machado

Re: Dúvida

por Rafael Franco -
A gente sabe que existe este método. Queremos saber como fazemos para carregar efetivamente os valores gerados na classe DecriptoRSA em variáveis da classe CriptoRSA. 
Em resposta à Rafael Franco

Re: Dúvida

por César Machado -
Para testar o programa enquanto vc esta fazendo, vc pode usar o atributo direto da outra classe. Ex:

DecriptaRSA decriptador = new DecriptaRSA();
CriptaRSA encriptador = new EncriptaRSA();
decriptador.geraChaves()
encriptador.carregaChavePublica(decriptador.n, decriptador.e) /* sendo que a classe DecriptaRSA tem atributos 'n' e 'e'. */

Mas o mais 'certo' seria digitar os numeros manualmente ou copiar e colar (acho que 'n' e 'e' devem ser private, então vc não vai poder fazer mais isso qdo tiver acabado)
Em resposta à César Machado

Re: Dúvida

por Rafael Franco -
Mas se fizermos "decriptador.n" e "decriptador.e", não estaremos tentando chamar métodos de nomes "n" e "e" respectivamente ao invés das variáveis desejadas?
Em resposta à Rafael Franco

Re: Dúvida

por César Machado -
não. Se vc fizer 'decriptador.n()' ele procura um método chamado n. Se vc colocar só 'decriptador.n' ele retorna o valor do atributo, mesmo se existisse algum método com o nome "n". ex:

class Lalala
{
  int n = 1;
  int n()
  {
    return 2;
  }
}

no painel de interações:
Lalala a = new Lalala();
a.n
> 1
a.n()
> 2
Em resposta à César Machado

Re: Dúvida

por Alfredo Goldman -
Olás,
  É interessante estar ciente que apesar de ser possível o acesso direto a um
atributo, esta prática é condenável quando se usa orientação a objetos pura.
Sempre que for necessário alterar ou consultar um atributo é interessante escrever
um método para isto.

Alfredo
Em resposta à Alfredo Goldman

Re: Dúvida

por Rafael Franco -

No método void geraChavesovo, pode definir o tamanho máximo dos primos aleatórios entre parênteses?

Por exemplo, void geraChaves(long tamanhoMax) ao invés de apenas void geraChavesovo.

Além disso, podemos criar métodos adicionais nas classes?

Em resposta à Rafael Franco

Re: Dúvida

por Julian Monteiro -
Oi Rafael,

1) pode adicionar um parametro no geraChaves;
2) pode criar métodos adicionais a vontade;


Em resposta à Julian Monteiro

Re: Dúvida

por Diogo José -
Quando eu faço:


while (leitor.chegouAoFim() == false)
    {
      char c = leitor.leChar();
      t = (long) c;

eu estou transformando os caracteres no padrão ASCII???
Em resposta à Diogo José

Re: Dúvida

por Julian Monteiro -
Sim, está, e é para fazer isso mesmo sorriso

Os caracteres (letras,espacos,algarismos) quando gravados em um arquivo são representados por números, que vão de 0 a 255.  E isso é feito de uma maneira padrão, através da tal tabela ASCII. Nela as letras de A a Z são representadas pelos números 65 a 90, as minúsculas 'a' até 'z' pelos números 97 a 122.

Veja a tabela completa aqui:
http://www.ime.usp.br/~pf/algoritmos/apend/iso-8859-1.html

(Note que ASCII são os números de 0a127, a partir daí tem-se a tabela extendida e é usada para os caracteres específicos de cada lingua... em português usamos a extensão para linguas latinas : iso-8859-1)

Por exemplo, a palavra "duvida" é representada no arquivo pela sequência de números: 64 75 76 69 64 61

é isso,
Julian
p.s. hoje esta tabela esta sendo substituida por esquema mais universal, o UTF-8

Em resposta à Julian Monteiro

Re: Dúvida

por Eduardo Grondona -

para passar de long a char (o contrário de (long) c, quál é o comando?

por exemplo: 63= long('?')

o contrário ?= ....(63)

Posso usar raíz quadrada do número para testar se um número é primo (não sei se pertence à biblioteca math).

Obrigado.
Eduardo.

Em resposta à Eduardo Grondona

Re: Dúvida

por Diogo José -
Para passar caractere para 'números' vc usa o seginte:

char c;
long t;
t = (long) c

daí vc pode trabalhar com t para fazer os cálculos necessários.

Obs.: Esses comandos vão pegar um caractere c e transformálo no padrão ASCII.

O inverso tb é válido! Desde que t esteja no padrão ASCII.
Em resposta à Diogo José

Re: Dúvida

por Eduardo Grondona -

José, se quero passar de long para ascii, quál é o comando?

Se coloco por exemplo:

char car=(long) z

Onde z é um long tenho:

found   : long
required: char

(long) devolve um long e não um char.

Obrigado.

Eduardo.

Em resposta à Eduardo Grondona

Re: Dúvida

por Diogo José -
O que vc vai ter que fazer é ler o arquivo de entrada.

Para isso os professores disponibilizaram uma classe chamada "Leitor".
Daí vc pode criar um objeto, char c = leitor.leChar() por exemplo, e fazer t = (long) c. Obs.: c = leitor.leChar(), leitor é objeto da classe Leitor.

Na página 4 do enunciado tem um exemplo de uso para ler um arquivo caractere a caractere, imprimir o valor lido na tela e gravá-lo em outro arquivo; mas esse exemplo lê e grava o que vc leu. vc tem que implementar algumas coisas entre "lê" e "gravar". No exemplo do enunciado o objeto da classe Leitor é entrada, e não leitor.

Acho que é isso!

Diogo José
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por tadashi mori -

Posso usar vetores para fazer esse ep?

Em resposta à tadashi mori

Re: Enunciado do EP2

por tadashi mori -
outra pergunta, no enunciado diz que os numeros primos devem ser menores que 512, mas em outra parte pede para o usuario especificar o numero maximo que o primo pode ter,  eu devo fixar 512 ou não?
Em resposta à Julian Monteiro

Observações no enunciado

por Diogo José -
2.2 Como Encriptar

De posse da chave pública, para Alice enviar um texto para Bob ela precisa encriptar os dados caractere por caractera. Cada letra t será codificada em um inteiro c da seguinte maneira:

    c = te mod n

Comentário: Se queremos fazer exatamente como está no exemplo do enunciado (2.5), de possa da chave pública (no caso n = 133 e e = 5), devemos fazer:

    c = t^e % n

Mas não é isso que diz no ítem 2.2; observe este exemplo:

    Vamos determinar o resto da divisão de 560 por 26.
    Escrevendo 560 = 26q + r, o problema equivale a determinar o inteiro r tal que 0 ≤ r ≤25 e tal que 560 ≡ r (mod 26).
    Isto é (em linguagem computacional) r = 560 % 26.

Isto vem da definição de "conguências":

    Seja m diferente de 0 um inteiro fixo. Dois inteiros a e b dizem-se congruentes múdulos m se m divide a diferença a - b.
   
Nesse caso, escrememos ab (mod m). (Gauss escreve nas Disquisitiones que foi induzido a utilizar o símbolo ≡ devido à grande analogia com a igualdade algébrica.)
    Com essa definição, a ≡ b (mod m) se e somente se ImI | (a - b), ou, equivalente, se existe um inteiro q tal que a = b + mq.
    Assim em a ≡ b (mod m), b é o resto da divisão de a por m quando 0 ≤ b ≤ m.

Logo, o correto no ítem 2.2 seria escrever te ≡ c mod n, e não c = te mod n.

Pois se fizermos c ≡ te mod n estaremos dizendo que t^e = c % n (que aliás também é correto, pois se a ≡ b (mod m), então b ≡ a (mod m)), mas daí fica diferente da forma que é apresentada no exemplo do enunciado em que temos que fazer c = t^e % n.

Da mesma forma, no ítem 2.3 o correto seria escrever cd ≡ t mod n, e não t = cd mod n.

É isso!

Diogo José
Em resposta à Diogo José

Re: Observações no enunciado

por Marcos Paulo Marins Nogueira Nune -
Esse problema para encriptar também ocorre para descriptar?
Em resposta à Marcos Paulo Marins Nogueira Nune

Re: Observações no enunciado

por Diogo José -
Não chega a ser um problema. Se vc fizer como está no exemplo do enunciado tudo ocorrerá como previsto.

O que eu chamei a atenção foi para a forma que está escrito no enunciado nos ítens 2.2 e 2.3 (incorreta para a situação).
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por Paulo M. F. -
Estou tendo um pequeno problema com o método geraPrimo

No enunciado do EP, especifica-se que tamanhoMax, a ser carregado melo método, deve ser do tipo lang, mas o gerador só carrega valores de 0 a N com N do tipo Int. Quando tento usar uma variável do tipo lang, o Dr Java acusa um erro de sintaxe.
O que devo fazer? Converter a variavel de entrada da classe de lang para uma variavel int? Poderia usar uma variavel inr de entrada, ao inves de lang?
Em resposta à Paulo M. F.

Re: Enunciado do EP2

por Paulo M. F. -
correção: long ao inves de lang, e int ao inves de inr, no final da msgem...
Em resposta à Paulo M. F.

Re: Enunciado do EP2

por Diogo José -
Vc pode fazer um truque: converter a variável de entrada long (512 no caso do EP) para int, gerar o número aleatório (int) (primo menor que 512) e depois converter para long.

Não seria interessante vc gerar os números aleatórios como int, pois o n e o m vai depender desses primos asssim como o d e o e vai depender de n e m. É interessante que todos os números sejam do tipo long para evitar problemas com números grandes.
Em resposta à Julian Monteiro

Dúvida ao ler/gravar

por Hugo Posca -
Olá a todos!
Quando tento ler um arquivo usando a classe Leitor ele dá erro e fala que não foi possível encontrar o arquivo entrada.txt - o sistema não pode encontrar o arquivo especificado-, já criei o arquivo na pasta do ep, em alguma pasta refrenciada pelo drJava, mas nada, continua dando o mesmo erro.
Até criei um saida.txt vazio pra ver se precisava dos dois ao mesmo tempo, mas num adiantou nada!

Que que eu faço agora? perplexo
Sem isso o EP não vai pra frente!!

Obrigado a todos!!!
Em resposta à Hugo Posca

Re: Dúvida ao ler/gravar

por Diogo José -
O método Leitor não procura os arquivos em uma pasta específica como, por exemplo, na pasta do EP.

O que ele faz é ler o endereço completo, por exemplo D:\Meus Documentos\Textos\Entrada.txt, e abrí-lo. Se vc não especificar o endereço completo o método vai acusar erro. O mesmo vale para o arquivo de saída.

Não se esqueça de colocar o endereço entre parenteses.

É isso!

Diogo José
Em resposta à Diogo José

Re: Dúvida ao ler/gravar

por Eduardo Grondona -

Estou colocando e aparece:

entrada.abre(C:\Meus documentos\Nova pasta\mac110\prova.txt);
Syntax Error: ":"

que tem que ir entre parénteses?

Obrigado.

Eduardo.

Em resposta à Eduardo Grondona

Re: Dúvida ao ler/gravar

por Diogo José -
O endereço tem que ir dentro de aspas duplas ex.: entrada.abre("C:\Meus documentos\Nova pasta\mac110\prova.txt");
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por Rubens Schmidt -

ermm, tipo, eu e minha dupla nao entendemos como calcula mod m sozinho?

qual seria a formula pra isso?

pq pra calcular o d*emodm td bem , mas na hora de calculas c=t^e mod n enguica :/

por favor respondam!!!

Em resposta à Rubens Schmidt

Re: Enunciado do EP2

por Diogo José -
Dá uma olhadinha em Observações no enunciado logo acima. Se ainda sim persistirem as dúvidas poste aqui novamente que tentaremos te ajudar.

Diogo José
Em resposta à Julian Monteiro

Re: Alguem Tentou compilar os arq. de leitura e gravação

por Natália Fazzani -

Ao fazer isso ele dá erro, na verdade 16 erros compilando os arquivos sozinhos

o Dr.Java diz a class do tipo FileReader, StreamTokenizer, IOException não existem. O que de fato acontece!!!!!

Algeum Sabe o PQ???????

Em resposta à Natália Fazzani

Re: Alguem Tentou compilar os arq. de leitura e gravação

por Diogo José -
O início do seu arquivo .java tem que ter a seguinte "cara":

import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.StreamTokenizer;

class.........

Isso não pode vir depois de alguma coisa, a não ser que seja comentário o que vem antes.

Diogo José
Em resposta à Diogo José

.

por Thaícia Stona de Almeida -
Sou do bmac mas estou assistindo as aulas com a turma do bma. A turma do bmac usa C, e a manhã usa java. Já faz quase 1 mes que eu estou assistindo as aulas mas apesar de estar conseguindo fazer os exercicios propostos na aula, ainda nao sei coisas basicas,  tipo como inserir uma função dentro de outra, se classe é que começa com letra maiúscula , enfim, essa parte caracteristica de java. Entendo os algoritmos, mas nem sempre sei como escreve-los corretamente. Ainda nao consegui achar um monitor para me ajudar. Sera que voces podem me passar o horario da monitoria? Ou poderiam tirar algumas duvidas por e-mail mesmo?
Obrigada
Em resposta à Thaícia Stona de Almeida

Re: .

por Rafael Franco -

Horários de Monitoria

 Segunda Julian Monteiro 15:00~16:00
  Terça   Ulisses Hayashida 16:00~17:00
  Quarta  Felipe Trevizan 16:00~17:00
  Quinta  Ernesto Colla 15:00~16:00
  Sexta   Paulo Cheque 12:00~13:00 (novo horário)

Ou vc pode tentar resolver suas dúvidas aqui pelo PACA mesmo.

Em resposta à Thaícia Stona de Almeida

Re: .

por Alfredo Goldman -
Olá,
  Vou responder a algumas das suas perguntas:
1) Não se insere um método/função dentro de outra, o quê se faz é criar classes
com diversos métodos (que correspondem as funções em C). A partir das classes,
objetos podem ser criados e os métodos podem ser chamados;
2) O padrão para nome de classes é XxxxXxxxXxxx (ex: CalculadoraCientífica)
para variáveis/atributos  e métodos usa-se a primeira letra minúscula no padrão
xxxXxxxXxxx (ex: void carregaDados(int a)). Este é um padrão, não uma regra rígida;
Tente tirar as suas dúvidas com os monitores e colegas.

Alfredo
Em resposta à Alfredo Goldman

Entrega do EP

por Rafael Franco -
Como faço para entregar um EP feito em dupla, já que o primeiro fiz individualmente?
Em resposta à Rafael Franco

Re: Entrega do EP

por Julian Monteiro -
Olá,
Cada integrante deve entregar uma cópia (idêntica) do trabalho.

Lembrem-se:
* Colocar o nome dos dois integrantes no cabeçalho do arquivo;
* Os trabalhos devem ser entregues em um arquivo Zip,
 contendo os arquivos java, alguns arquivos de exemplo
(encriptado e decriptado) e as simulações no DrJava correspondentes...
(i.e. contendo as chaves públicas e privadas visíveis na simulação)
* Para facilitar a correção, pedimos para colocar o seu nome no arquivo Zip entregue:
 - Se individual:  ep2-SEUNOME.zip
 - Se feito em dupla:  ep2-dupla-NOME1-NOME2.zip
 
[]s
Julian

Em resposta à Diogo José

Re: Alguem Tentou compilar os arq. de leitura e gravação

por Julian Monteiro -
Olás,
Estas linhas 'import ...' (para usar classes da biblioteca do java)
somente são necessárias no arquivo contendo a classe LeitorGravador.
O seu arquivo MiniRSA.java não deveria conter linhas deste tipo...

Natália, vc já solucionou o problema?

[]s
Julian
p.s. Diogo, César, Rafael, ... muito legal a participacão de vocês aqui. Tks
Em resposta à Julian Monteiro

Re: Alguem Tentou compilar os arq. de leitura e gravação

por Natália Fazzani -

SIM, Julian..

já solucionei meus problemas sim (eu acho!!) quanto aos erros na hora de compilar....muito obrigada pela preocupação!!

Mas surgiu uma nova dúvida:

Na hora de Encriptar um arquivo, vc deve estabelecer as chaves, que são geradas aleatoriamente na classe que decripta. Porém, quando vc escreve um texto, vc primeiro o encripta para primeiro decriptá-lo certo?!

 Pois então, como que vou encriptar se ainda naum sei as chaves que serão geradas na hora de fazer o inverso (decriptar)?!?

Em resposta à Natália Fazzani

Re: Alguem Tentou compilar os arq. de leitura e gravação

por Diogo José -
Primeiro vc vai gerar as chaves na classe DecriptoRSA; logo em seguida vc vai carregar a chave pública na classe CriptoRSA pelo método void carregaChavePublica(long n, long e).

Daí vc pode encriptar o arquivo. Para decriptar, como a chave privada já está carregada, é só usar o método decriptaArquivo.

Ao meu ver seria interessante que fosse criado um método carregaChavePrivada na classe DecriptoRSA pois da forma que está no enunciado, de posse da chave privada (sem que ela seja gerada imediatamente) fica quase impossível decriptar o arquivo, visto que vc deverá gerar chaves até os primos conhecidirem.

Isso pode ser observado por exemplo quando eu gero as chaves numa segunda-feira, por exemplo, encripto um arquivo e vou decriptá-lo só na sexta-feira. Ou seja, o Dr. Java não vai ter minha chave privada guardada na memória até e dia da decriptação.

Assim seria viável criar um método que carregasse a chave privada.

Diogo José
Em resposta à Diogo José

Re: Alguem Tentou compilar os arq. de leitura e gravação

por Julian Monteiro -
Olás,

Concordo com a idéia do método para carregar a chave privada. Boa idéia sorriso.
Quem quiser, fique a vontade para implementá-lo.
Na verdade, ele ajudará bastante nos testes.

Só lembrando, uma outra maneira para gerar sempre os mesmos valores de números primos é colocar uma semente no gerador aleatório  (gerador.setSeed(12345)),
com isso, os números aleatórios gerados sempre seguirão a mesma sequência.... (pra cada semente, tem-se uma sequência diferente).

[]s
Julian
Em resposta à Julian Monteiro

Duvida em relação aos longs

por Daniel Santos -

Olá.. quando tento criar uma variável LONG o drjava diz..

tipo

long a;

Only the primitive types "int", "double", "boolean", and "char" can be used at the Advanced level

oq eu faço???

Em resposta à Daniel Santos

Re: Duvida em relação aos longs

por Diogo José -
Não entendi o que o Dr. Java quis dizer.

Coloque o método aqui para que possamos verificá-lo.

Diogo José
Em resposta à Daniel Santos

Re: Duvida em relação aos longs

por Julian Monteiro -
No menu 'Language level' do DrJava tem um checkbox,
troque para 'Full java', dai ele vai deixar você fazer de tudo!...

Em resposta à Julian Monteiro

Re: Duvida em relação aos longs

por Rafael Franco -
Quando eu executo o geraChaves(), os valores de n, d, e ficam carregados na classe DecriptoRSA.
Para encriptar um arquivo, necessariamente devo carregar valores para a chave pública na classe EncriptoRSA, já que os valores da chave foram gerados em outra classe.
Optei por implementar o método carregaChavePrivada() na classe DecriptoRSA. Contudo, ao tentar decriptar um arquivo SEM carregar valores na chavePrivada, obtenho êxito, concluindo assim que a chave privada fica automaticamente carregada após a execução do geraChaves().
Considerando que o método carregaChavePrivada() é facultativo, posso descarregar a chave privada após a execução do geraChaves() para que o decriptaArquivo() funcione se, e somente se, eu carregar a chave privada?
Em resposta à Rafael Franco

Re: Duvida em relação aos longs

por Rafael Franco -
Outra dúvida: posso mudar o método divulgado no paca para, após executar o decriptaArquivo(),  imprimir na tela os caracteres que estão sendo gravados no arquivo de saída, visando assim uma maior rapidez no processo de decodificação?
Em resposta à Rafael Franco

Re: Duvida em relação aos longs

por Julian Monteiro -
Porque isso deixaria a decodificacão mais rápida?
Em resposta à Julian Monteiro

Re: Duvida em relação aos longs

por Diogo José -
    Se mudarmos o método de forma que ele não imprima no painel de iterações do Dr. Java o que está sendo decodificado obteremos uma melhor eficiência pois a porcentagem do processador que estaríamos usando para tal agora pode ser totalmente usada para fazer os cálculos matemáticos.

    No meu PC consegui uma resposta até 40% mais rápida.

    Ah, se não imprimirnos na tela tb o que está sendo codificado a resposta fica até 95% mais rápida!!

Diogo José
Em resposta à Diogo José

Re: Duvida em relação aos longs

por Julian Monteiro -
Vc deve imprimir na tela somente quando estiver testando o programa,
o projeto entregue deverá gravar as saídas no arquivo.

Vc está certo, o processo de imprimir na tela é bem lento...
(se vc quer um programa mais rápido, precisa implementar o método potenciaMódulo de forma eficiente, usando a técnica de exponênciacão modular: http://en.wikipedia.org/wiki/Modular_exponentiation  -- item obrigatório para o pessoal do BCC).

[]s


Em resposta à Julian Monteiro

Re: Duvida em relação aos longs

por Diogo José -
    De fato utilizamos a técnica de exponenciação modular.

Grato,

Diogo José
Em resposta à Rafael Franco

Re: Duvida em relação aos longs

por Julian Monteiro -
Oi Rafael,
Acho melhor deixar os valores da chave privada na classe mesmo, e não apagá-los,
dado que vocês estão fazendo um exercício.
Bem com como vc comentou, o método carregaChavePrivada() é facultativo e portanto ele não pode alterar o funcionamento do resto sorriso

[]s
Ju
Em resposta à Julian Monteiro

Dúvida extra-EP

por Diogo José -
    Olá,

    Estive observando as chaves geradas com os números primos majorados por 512 e vi que facilmente pode-se descobrir, de posse da chave pública, a chave privada!

    Resolvi então gerar primos maiores; primeiro tentei gerar primos da ordem de 2^20, feito! Foram geradas todas as chaves, mas na hora de carregar a chave publica (da ordem de 2^34) apareceu no painel de iterações o seguinte:

        Welcome to DrJava.
        > CriptoRSA c = new CriptoRSA();
        > DecriptoRSA d = new DecriptoRSA();
        > d.geraChaves(1024*1024);
        Chave pública (n, e): (16193391131, 5)
        Chave privada (n, d): (16193391131, 6477254573)
        > c.carregaChavePublica(16193391131, 5);
          NumberFormatException: For input string: "16193391131"
          at java.lang.NumberFormatException.forInputString(Unknown Source)
          at java.lang.Integer.parseInt(Unknown Source)
          at java.lang.Integer.valueOf(Unknown Source)
        >

    Já para gerar primos da ordem de 2^40 apareceu o seguinte no painel de iterações:

        Welcome to DrJava.
        > CriptoRSA c = new CriptoRSA();
        > DecriptoRSA d = new DecriptoRSA();
        > d.geraChaves(1024*1024*1024*1024);
          IllegalArgumentException: n must be positive
          at java.util.Random.nextInt(Unknown Source)
          at DecriptoRSA.geraPrimoAleatorio(MiniRSA.java:98)
          at DecriptoRSA.geraChaves(MiniRSA.java:174)
          at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
          at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
          at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
          at java.lang.reflect.Method.invoke(Unknown Source)
        >

    Como proceder para resolver esses impasses?

Diogo José
Em resposta à Diogo José

Re: Dúvida extra-EP

por Julian Monteiro -
Diogo,

* Sobre o primeiro erro (NumberFormatException): O DrJava espera receber números do tipo 'int', mas o número que vc digitou é grande demais e extrapolou a capacidade. Para solucionar isso, avise-o que o número é um 'long', colocando um L maiúsculo no final: 16193391131L

* O segundo erro (  IllegalArgumentException: n must be positive) também aconteceu porque vc extrapolou o valor do int, mas dessa vez o número resultante ligou o último bit tornando o seu número negativo (o último bit diz se o número é positivo ou negativo).

* Mas, independente disto, o seu EP nao iria funcionar com primos tão grandes... nós estamos limitados a trabalhar com o tipo long (64 bits) e, se fizermos uma análise simplista, chegaremos no valor máximo de p e q em: 32768 (15 bits).

Dado que 'n = p*q' (potencialmente um número de 15+15 = 30 bits), e sabendo que no meio do trabalho fazemos multiplicacões com n e m ( 30 bits/cada ), precisamos portanto  de 60 bits para guardar os resultados (antes de fazer mod)....
e isso cabe em um long!.

Para resolver esses impasses, você precisaria criar uma classe para trabalhar com números grandes (> 64), e ela precisaria conter alguns atributos do tipo long para guardar os números e métodos do tipo: soma, multiplicacão, modulo, etc... é um exercício legal!

Abracos,
Julian
Em resposta à Julian Monteiro

Re: Dúvida extra-EP

por Rafael Franco -
Dúvidas:
1. Como vc chegou no número 32768?
2. Onde é usada a multiplicação de n por m no EP?
3. Além dos atributos do tipo long, deveria haver atributos que guardassem números maiores do que 64 bits, por exemplo, um atributo para guardar o produto entre dois números de 64 bits. Como o limite do tipo long é 64 bits, tal atributo não poderia ser long. Como proceder?
Em resposta à Rafael Franco

Re: Dúvida extra-EP

por Julian Monteiro -
oi,

> 1. Como vc chegou no número 32768?
Resp: Vou tentar explicar ao contrario:
Estamos restritos ao long (8 bytes == 64 bits), que tem capacidade absoluta máxima de (263 -1). No método potenciaModulo, ao decriptar, vc terá que multiplicar num*num, e o resultado tem que caber em um long, então, cada 'num' TEM que ser <= (2 31-1).
Como 'num' é o um número encriptado, sabemos que passou por um 'mod n',
então a restricão de 'num' será a dada por 'n' ( <= 231-1). Mas como n = p*q, o tamanho máximo de p e q terá que ser (2^15 - 1), que é o valor 32767 ...

(Talvez isso aqui ajude: se eu multiplicar dois números de 4 bits cada, o resultado será um número de 8bits, exemplo: 13 em binário é '1101', se eu fizer 13*13 = 169, em binário '10101001')

>2. Onde é usada a multiplicação de n por m no EP?
Resp: não é, escrevi errado...

>3. Além dos atributos do tipo long, deveria haver atributos que guardassem números maiores do que 64 bits, por exemplo, um atributo para guardar o produto entre dois números de 64 bits. Como o limite do tipo long é 64 bits, tal atributo não poderia ser long. Como proceder?

Resp: Não há tipos nativos em Java que guardam mais que 64 bits, vc terá que implementar uma classe para simular isso. Por exemplo, se vc quer fazer contas com números de 128 bits, precisará criar uma classe com dois atributos do tipo long (64 cada), e criar os métodos matemáticos na mão. Como fazer as contas então? vc vai ter á que "escovar bits" sorriso. Não poderá simplesmente multiplicar um pelo outro com o sinal '*', terá que usar técnicas alternativas, veja aqui: http://en.wikipedia.org/wiki/Binary_numeral_system

Em resposta à Julian Monteiro

DECRIPTAR???

por Natália Fazzani -

Na hora de decriptar o meu texto aparecem uns quadrados e eu não sei o que fazer!!!!!

Qual é o problema hein?!?

(POR fAVOR....me ajudem!! heueheu)

Em resposta à Natália Fazzani

Re: DECRIPTAR???

por César Machado -
Provavelmente tem alguma conta errada...
Os quadrados aparecem quando voce tenta colocar um caractere que não existe...

Tenta pegar a primeira letra do arquivo que voce esta encriptando e fazer as contas "manualmente" (em vez de usar o método decripta direto, usa o potenciaModulo), e compara o resultado com o primeiro numero do arquivo encriptado. Se for igual tenta decriptar do mesmo jeito. Se aparecerem numeros diferentes, é porque você colocou alguma conta errada no meio...

Se mesmo assim, você conseguir os mesmos resultados "manualmente", mas o numero final da decriptação é diferente do caractere original (ex: para a letra 'a', a decriptação tem que devolver 97), então o erro deve estar em potenciaModulo (vê se vc encripta com potenciaModulo(x, e, n) e decripta com potenciaModulo(x, d, n) (x é o caractere ou numero do arquivo de entrada..)
Em resposta à César Machado

Re: DECRIPTAR???

por Julian Monteiro -
Olás,

Complementando a resposta do César:
Se o seu EP de vez em quando funciona e de vez em quando não (aparecem quadradinhos!), então provavelmente tem algum problema relacionado aos números aleatórios.

Existem algumas restricões mínimas nos valores de p e q que não estão explicitas no enunciado...

Dica: Ao encriptar nós usamos o resto da divisão por n ( % n).
Qual é o intervalo resultante de x % n?
Quantas números são representados (existem) na tabela ASCII?

[]s



Em resposta à Julian Monteiro

Re: Dúvida extra-EP

por Diogo José -

Olá,

No nosso método potenciaModulo nós não multiplicamos num*num, implementamos uma técnica que usa apenas restos de divisões sucessivas e multiplicações com números extremante pequenos.
Assim, acho que a única restrição seria para n, pois n = p*q, donde temos que p e q <= 232 - 1. Caso contrário acho que n 'estouraria'.

Resp: Não há tipos nativos em Java que guardam mais que 64 bits, vc terá que implementar uma classe para simular isso. Por exemplo, se vc quer fazer contas com números de 128 bits, precisará criar uma classe com dois atributos do tipo long (64 cada), e criar os métodos matemáticos na mão. Como fazer as contas então? vc vai ter á que "escovar bits" . Não poderá simplesmente multiplicar um pelo outro com o sinal '*', terá que usar técnicas alternativas, veja aqui: http://en.wikipedia.org/wiki/Binary_numeral_system

Não entendi muito bem... vc quiz dizer que para guardar um número de 128 bits (ou mais) tenho que guardá-lo em dois atributos (ou mais) distintos, por exemplo um número de 96 bits eu terei que guardá-lo em dois atributos de 48 bits?
Mas e para dividir, fazer mod ou qualquer outra operação não ficaria impossível, pois o número de 96 bits é, na verdade, dois números...

Se não for abusar demais tenho outras dúvidas...

No painel de iterações do Dr. Java consigo gerar primos de até 30 bits. Mas quando exporto para o prompt de comando e tento gerar primos de 30 bits aparece uma mensagem de erro:

C:\Documents and Settings\Diogo José\Desktop\MiniRSA>java MiniRSA
Digite '1' se vc deseja encriptar um arquivo ou digite '2' se vc deseja decripta
r um arquivo
1
Entre com o tamanho ma'ximo dos primos
1024*1024*1024
Exception in thread "main" java.util.InputMismatchException
at java.util.Scanner.throwFor(Unknown Source)
at java.util.Scanner.next(Unknown Source)
at java.util.Scanner.nextLong(Unknown Source)
at java.util.Scanner.nextLong(Unknown Source)
at MiniRSA.main(MiniRSA.java:37)

Já no Dr. Java (Run Document's Main Method F2) aparece o seguinte:

Welcome to DrJava.
> java MiniRSA
Digite '1' se vc deseja encriptar um arquivo ou digite '2' se vc deseja decriptar um arquivo
Entre com o tamanho ma'ximo dos primos
InputMismatchException:
at java.util.Scanner.throwFor(Unknown Source)
at java.util.Scanner.next(Unknown Source)
at java.util.Scanner.nextLong(Unknown Source)
at java.util.Scanner.nextLong(Unknown Source)
at MiniRSA.main(MiniRSA.java:37)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(Unknown Source)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(Unknown Source)
at java.lang.reflect.Method.invoke(Unknown Source)
>

O que devo fazer para corrigir todos esses erros?


Se vc quiser dar uma olhada no código da classe MiniRSA:

class MiniRSA
{
  public static void main(String[]arg)
  {
 
    System.out.println("Digite '1' se vc deseja encriptar um arquivo ou digite '2' se vc deseja decriptar um arquivo"); 
    Scanner prin1 = new Scanner(System.in);
    String a = prin1.next();
    long int1 = Integer.parseInt(a);
 
    if (int1 == 1)
    {
      Scanner sc = new Scanner(System.in);
      DecriptoRSA d = new DecriptoRSA();
      System.out.println("Entre com o tamanho ma'ximo dos primos");
      long x = sc.nextLong();
      d.geraChaves(x);
 
      //Encripta
 
      System.out.println("Carregue a chave pu'blica");
      CriptoRSA c = new CriptoRSA();
      Scanner n1 = new Scanner(System.in);
      Scanner e1 = new Scanner(System.in);
      long n = n1.nextLong();
      long e = e1.nextLong();
      c.carregaChavePublica(n, e);
 
      System.out.println("Digite o end. do arquivo a ser encriptado (Sem aspas)");
      Scanner ent1 = new Scanner(System.in);
      String ent = ent1.next();
 
      System.out.println("Digite o end. do arquivo codificado (Sem aspas)");
      Scanner cod1 = new Scanner(System.in);
      String cod = cod1.next();
 
      c.encriptaArquivo(ent , cod);
    }
    else if (int1 == 2)
    {
      DecriptoRSA d = new DecriptoRSA();
 
      //Decripta
 
      System.out.println("Carregue a chave privada");
      Scanner n2 = new Scanner(System.in);
      Scanner d1 = new Scanner(System.in);
      long nd = n2.nextLong();
      long d_ = d1.nextLong();
      d.carregaChavePrivada(nd, d_);
 
      System.out.println("Digite o end. do arquivo a ser decriptado (Sem aspas)");
      Scanner dec1 = new Scanner(System.in);
      String dec = dec1.next();
 
      System.out.println("Digite o end. do arquivo decodificado (Sem aspas)");
      Scanner decod1 = new Scanner(System.in);
      String decod = decod1.next();
 
      d.decriptaArquivo(dec, decod);
    }
  }
}


Atenciosamente,

Diogo José



Em resposta à Diogo José

Re: Dúvida extra-EP

por Julian Monteiro -
Olá Diogo,

1) Sobre os erros (que na verdade é um só): O Java é burro, ele não sabe que 1024*1024*1024 é um número, vc precisa fazer a conta e passar o valor pra ele...

2) Vc está se referindo à exponênciacão modular, não?
Se for, vc terá:  num*algo (num passou por 'mod n', que será no seu exemplo: 2^60)... e por mínimo que seja 'algo' (por exemplo, o número 60 de 5bits), você vai extrapolar as suas contas... 61+5 = 66 bits (e não cabe no long... note que vc precisa levar em conta o valor da multiplicacao antes de fazer o mod).
A unica maneira que penso ser possivel utilizar valores mairoes de p e q (>32767) é "escovando bits"... não sei se é o seu caso.

3) Sobre os números de 128 bits, é isso mesmo que vc pensou sorriso, dois atributos de 64 bits/cada. Vc só pecou qdo comentou do 96bits, para esse caso vc precisará dos mesmos dois atributos de 64 - que é a sua "unidade mínima" - (daí vc irá guardar 64 bits em um e 32 em outro).... na realidade, vc vai implementar isso como um vetor de longs.

Sim, pra fazer as contas vc vai ter um trabalhinho, mas É possível sim sorriso, usando matemática binária (procure referências sobre aritmética de precisão arbitrária).

Espero ter ajudado,
[]s
Julian

p.s. Se quiser encurtar o caminho, dê uma olhada na classe BigInteger da biblioteca do Java.... internamente ela usa ints ou longs (nao lembro).
Em resposta à Julian Monteiro

Re: Enunciado do EP2

por Alex Morinaga -
Eu sei q já está mto em cima da hora, e n me importo mto em n ser respondido ._.
Mas tenho uma dúvida.. ou 2, sei lá.
-c sempre será menor q n, pois é o resto da divisão por ele, n? Então, caso n seja mto pequeno, n teria perigo de 2 ou + letras receberem o msm valor de c?
-O valor devolvido na decriptação é o msm que o valor da letra qdo encripta, certo? bem, tentei fazer o código, dps na mão msm, e, usando as fórmulas do enunciado, n cheguei no resultado =x
As fórmulas sempre darão certas, têm exceção, ou eu q tô fazendo algo de errado? >_>;
Em resposta à Alex Morinaga

Re: Enunciado do EP2

por Julian Monteiro -
Oi,
Eu acabei de escrever um mail sobre isso... coincidência!.

> c sempre será menor q n, pois é o resto da divisão por ele, n?
R: Certo

> Então, caso n seja mto pequeno, n teria perigo de 2 ou + letras receberem o msm valor de c?
R: Certissimo

> O valor devolvido na decriptação é o msm que o valor da letra qdo encripta, certo? bem, tentei fazer o código, dps na mão msm, e, usando as fórmulas do enunciado, n cheguei no resultado =x
R: Se n for pequeno, vai dar problema... triste

Então, qual o valor mínimo de n??

[]s