8 Replies - 358 Views - Last Post: 20 August 2012 - 03:01 PM Rate Topic: -----

#1 bladevetren  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 18-August 12

public key exponent generation error

Posted 20 August 2012 - 09:51 AM

hello, i am attempting to generate a publicKey exponent (e) where 1 < e < φ(n) (n=p*q)and the gcd(e,φ(n))= 1, and store this value in a variable.
i have attempted creating a code which completes this task but the resulting xml is not printed onto the console which is probably because φ(n) != (p  1)*(q  1). in conclusion how may i go about fixing this problem?
here is the code:
import java.io.StringWriter;
import java.util.Random;

import javax.xml.parsers.DocumentBuilder;
import javax.xml.parsers.DocumentBuilderFactory;
import javax.xml.transform.OutputKeys;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerFactory;
import javax.xml.transform.dom.DOMSource;
import javax.xml.transform.stream.StreamResult;

import org.w3c.dom.Comment;
import org.w3c.dom.Document;
import org.w3c.dom.Element;
import org.w3c.dom.Text;


public class publicKeygeneration {
	final static int p=(new Random()).nextInt();
	 final static int q=(new Random()).nextInt();
		
static int x = 1;

static int n = p*q;


public static int toiler(int c) {

int count = 0;

for(int i = 1; i < c; i++)
if(gcd(c,i) == 1)
count++;

return count;
}
public static int gcd(int x, int y) { 
	 while (y != 0) {
	  int r = x % y;
	  x = y; 
	  y = r;
	  }
	 return x;
	} 

public static int exponent(int k){
	
	 while(toiler(n)==(p-1)*(q-1))
		


			
				for(int e=2; e<k; e++)
				 
					if (1 == gcd(e, toiler(n)))
					k = e;
				
	 
					return k;
				
					
				}

	
	
	
			
			


	

	


	 public static void main(String [] args){
		 if(toiler(n)==(p-1)*(q-1)){
		int k = toiler(n);
			
			int exponent = exponent(k);
		 
		 String e = String.valueOf(exponent);
		 String c = String.valueOf(n);
	        try {
     DocumentBuilderFactory dbfac = DocumentBuilderFactory.newInstance();
     DocumentBuilder docBuilder = dbfac.newDocumentBuilder();
     Document doc = docBuilder.newDocument();

    
     Element root = doc.createElement("root");
     doc.appendChild(root);

     
     Comment comment = doc.createComment("data export");
     root.appendChild(comment);

 
     Element child = doc.createElement("data");
     child.setAttribute("PublicKey", e+" "+c);
     root.appendChild(child);


     Text text1 = doc.createTextNode("developed by bladevetren");
     child.appendChild(text1);

    
     TransformerFactory transfac = TransformerFactory.newInstance();
     Transformer trans = transfac.newTransformer();
     trans.setOutputProperty(OutputKeys.OMIT_XML_DECLARATION, "yes");
     trans.setOutputProperty(OutputKeys.INDENT, "yes");

     
     StringWriter sw = new StringWriter();
     StreamResult result1 = new StreamResult(sw);
     DOMSource source = new DOMSource(doc);
     trans.transform(source, result1);
    String xmlString = sw.toString();

     
    String i = "data:\n\n" + xmlString;
   System.out.println(i);
   
 } catch (Exception k23) {
     System.out.println(k23);
 }
	 }
}
}


Is This A Good Question/Topic? 0
  • +

Replies To: public key exponent generation error

#2 LaFayette  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 43
  • View blog
  • Posts: 326
  • Joined: 24-November 08

Re: public key exponent generation error

Posted 20 August 2012 - 10:04 AM

The exponent e is normally just picked to be a some prime (like 3 or 17). I don't know what you are doing though. Why is there no condition on p and q to be (distinct) primes in your code?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10568
  • View blog
  • Posts: 39,123
  • Joined: 27-December 08

Re: public key exponent generation error

Posted 20 August 2012 - 10:06 AM

While e can be prime, the important thing is that it is relatively prime to n. This will also result in it being relatively prime to phi(n).

Also, please properly indent/format your code so we can easily read and follow it.
Was This Post Helpful? 0
  • +
  • -

#4 bladevetren  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 18-August 12

Re: public key exponent generation error

Posted 20 August 2012 - 10:29 AM

i am intending to input the generation of prime integers at a later date as i am attempting to implement a method that creates n that won't be compromised once the disrbution of prime numbers is discouvered. also the reason why i have inputed the public key exponent like this is because it is needed in the multiplicative inverse which creates the privateKey. anyway is there a way which i could find a value of p and q where φ(n) = (p  1)*(q  1) and then start all other methods of the program?
Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10568
  • View blog
  • Posts: 39,123
  • Joined: 27-December 08

Re: public key exponent generation error

Posted 20 August 2012 - 10:32 AM

Phi(n) is generated from the two primes- p and q. You can't find it without p and q.

Quote

also the reason why i have inputed the public key exponent like this is because it is needed in the multiplicative inverse which creates the privateKey.

Not the multiplicative inverse, but the modular inverse. And once you have the public key, the private key is found using the extended Euclidean algorithm.

You might want to brush up on your RSA.
Was This Post Helpful? 0
  • +
  • -

#6 bladevetren  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 18-August 12

Re: public key exponent generation error

Posted 20 August 2012 - 10:52 AM

ahh i see, i was under the impression that the privateKey was generated only through calculating d as d=(e^-1)mod(φ(n)) not solving (d)mod φ(n) = 1 by euclids extended alorithm. also would it be possible to generate n by using a function of p and q such as (p*q)-q depending on the value of p and q or if p or q is abundant or deficiant?
Was This Post Helpful? 0
  • +
  • -

#7 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10568
  • View blog
  • Posts: 39,123
  • Joined: 27-December 08

Re: public key exponent generation error

Posted 20 August 2012 - 11:02 AM

You have to define n as the product of two primes.
Was This Post Helpful? 0
  • +
  • -

#8 blackcompe  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 1155
  • View blog
  • Posts: 2,533
  • Joined: 05-May 05

Re: public key exponent generation error

Posted 20 August 2012 - 02:08 PM

bladevetren: I went ahead and made an RSA implementation if your interested, but you seem to have the theory just about right.

I don't know whether you're planning to use your implementation in a production system, but if so, I highly recommended against it, as it's extremely hard to protect against all feasible attacks with little knowledge of what's out there these days. Even something as simple as generating p and q close to each other, can completely implicate your system. That's very easy to break, even with a big key size.

Here are a few things to consider in your code:

  • Use a secure random number generator. Java's Random class is not nearly secure. Any RNG that's predictable is by definition, insecure.
  • You should be using the BigInteger class. Your key sizes should be at least 1024 bits, which is hundreds of digits. Hypothetically, factoring a 32-bit modulus, N, shouldn't be all that hard (at least with a cluster of computers).
  • BigInteger has (efficiently) done all the work for you in calculating modular inverses, gcds, etc.


Above all, you should use the JCE when writing serious code. Here's a DIC snippet for that.

This post has been edited by blackcompe: 20 August 2012 - 02:08 PM

Was This Post Helpful? 0
  • +
  • -

#9 bladevetren  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 27
  • Joined: 18-August 12

Re: public key exponent generation error

Posted 20 August 2012 - 03:01 PM

thanks, by the way are you reffering to my idea of multi-functionality for the generation of n?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1