I have been searching for a few days now, but I cannot find a big-O notation algorithm for encrypting, decrypting, or attempting to break an encrypted file (brute force) making use of public key encryption. I am attempting to determine the big-O notation of an idea I have developed that makes heavy use of public key encryption.

What are these Big-O algorithms as related to public key encryption:

A) Encrypt a file made up of N characters with an L length key

B) Decrypt that same file

C) A typical brute force algorithm to break an encrypted file with N characters and with a maximum key length of L

Any included Big-O notations for more efficient algorithms for breaking the encryption would be appreciated. Also, reference to wherever this material can be found.

Sorry to ask a question that I really should be able to find on my own, but I haven't managed to come across what I am looking for.

Standard public/private key algorithms are almost never used on large inputs, as the security properties of these algorithms are generally not suitable for bulk encryption. The most common configuration is to use a public/private key algorithm to encrypt a small (constant-size, usually 128 - 256 bit) key, then use that key for a symmetric encryption algorithm.

That being said, I'll use RSA as a test case for the rest of the questions:

A/B) Setting aside key generation, RSA encrypts and decrypts in `O(n)`

for the size of the message. (Note that all messages must be the size of the key, so smaller messages are padded and larger messages must be broken up.) The exact speed of encryption/decryption depends on the algorithms used by your RSA implementation, but it's polynomial in key size:

http://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml

C) Given a public key, RSA can be cracked by factoring the public key, which is currently best accomplished using GNFS (which is `O(exp((7.1 b)^1/3 (log b)^1/3))`

). I don't believe there's much work on cracking RSA based on encrypted data, as the public key is a much more useful target.

Similar Questions

I am trying to encrypt and decrypt a message as mentioned in the below code. Basically I want to encrypt a message with a public key and convert that encrypted message from byte array to String. And d

Is there a public / private key encryption scheme that will not change a message's length? I would like to encrypt a message one packet at a time, but if the packet grows, it would no longer just be o

How do you setup server to server SFTP to use public-key authentication instead of user account and password?

One question about the public key. If I am using C code to do some RSA stuff, do I need to put \r\n or \n at the end of each line? Should I write a C string like this? -----BEGIN PUBLIC KEY-----

I have two AsymmetricAlgorithm objects that contain an RSA Private and RSA Public key. The private key was retrieved out of the Windows-MY keystore and the Public key from a user's certificate. How ca

When I create a user I will create a private and public key. The public key is the token id for the user. The private key will be used for encrypt and decrypt of data. When the user login, my Android

I am trying to implement symmetric encryption using AES where I specify a key and IV. Within each ecosystem (Java -> Java / .NET -> .NET) encryption and decryption works as designed, but if I tr

I want to encrypt the session key using the public key. How does the PGP software do this? Can somebody specify the procedure or function of encryption in Python?

As the M2Crypto library is not available for Python 3, I'm looking for a way to read in an X509 certificate, extract the public key from it and use it for RSA encryption. I currently have the followin

I am trying to find what is public key header and public key info. I have dumped a certificate in C format using openssl, along with public key modulus it listed public key info and public key header

I know RSA private key contains the information of the associated public key. How can I dump the public key from the private key? I want to do it in iOS environment without openssl. Is it possible?

How do the Public key fingerprint and Digital Signature differs ? Or both are same ? if they are different, what is the application of public key fingerprint ? Thanks

I have coded a simple test, but it sent me: Unverified, I guess because I am using the whole certificate instead of the public key. What method gives me public key? $rsa = new Crypt_RSA(); $rsa->

I have seen an example of encrypting a string with a Java Midlet, using a public key which is a byte array. I am not able to do that on a BlackBerry, because there is no X509EncodedKeySpec and Cipher

In an asymetric encryption scheme, I was wondering if it's possible to achieve the following: Bob sends to Alice his public key Alice alters Bob's public key and encrypt some document with it Alice s

For a homework assignment, I am asked to determine the algorithm used to generate a given cipher text. The key is also given. Currently, I am working down a list of simple encryption algorithms and se

I'm generating an encryption key to encrypt some sensitive data with the Rijndael (AES) encryption algoritm. I'm using a guid as key generator. Are these keys strong enough? Note: it is only sensiti

i need to encrypt my symmetric key which is in AES with my public key. I take my public key from server's certificate but i don't know how to encrypt my symmetric key with this public key in Windows P

The Problem: Retrieving a public key For an iPhone App, I need to create a rsa key pair, store it in the key chain and retrieve the public key. Fortunately, Apple released a Crypto Exercise Sample whe

I'm creating an app (C#) that is going to send some messages around the network. Outgoing messages will be signed by a private key, incoming messages decrypted with a private key. In case someone stea

I am encrypting the communication with the server in my blackberry app. I am using the RC4 encryption which needs a key to be provided. What's the best place to hide this key inside the application ?

I'm trying to access public activities from Google+ using the Google API. So I created a new project in the Developers Console, activated the Google+ API and created a key for browser applications (Pu

We are using Java + H2 Database in server mode, because we do not want users from accessing database file. To add more protection to database file, we plan to use AES encryption (add CIPHER=AES to da

After i red articles about Cryptography(Symmetric and Asymmetric) methods.Many articles are telling that Private key will be used to encrypt and decrypt.Public key will be used to encrypt.But When i t

I need crypto-algorithm AES in key wrap mode. Is there some open-source library or implementation that could be helpful? It is important, that it must be key wrap mode.

Consider a situation when two public keys of two different publishersâ€™ assemblies are mapped to the same public key token (while name, version and culture of the assemblies are also the same). When t

Is a dll with a strongname public key (snk) significantly slower than without ?

provisioning problem again. Refering to my question: http://stackoverflow.com/questions/609486/iphone-development-provisioning-assistant-step-3-public-private-key-problem I have another mac computer w

I have a 128 bit encryption key that I would like to break up into three parts that when XOR'ed together reproduce the key. How do I do this?

I'm getting my head around encryption and how encoding affects generation of the keys and initialization vectors. I'm working with a TripleDESCryptoServiceProvider which requires 24 byte key and 8 by

For an application I want to write, the webservice gives me this public key, with which I have to encrypt the password for signing in. But I don't know what kind of encryption this might be. Is this r

I have a signed data being passed to my server along with the public key in hex format, with which this data was signed. Hash algorithm is the same for all requests sha-256, but public keys are differ

Say I have this set up as my encryption key and I already have the encrypt library on autoload: $config['encryption_key'] = 'bjA{<ATCs1w5?,8N(bJvgO3CW_<]t?@o'; How do I use it in an encrypt func

I search for algorithm for file encryption/decryption which satisfies following requirements: Algorithm must be reliable Algorithm should be fast for rather big files Private key can be generated by

I've made 2 encryption algorithms, where one of them focuses on speed, and the other is a stronger encryption. The first encryption is this: public static byte[] Encrypt(byte[] bytes, string key) { by

I'd like to encrypt very little data (15 bytes to be exact) into a as short as possible (optimally, no longer than 16 bytes) message using a public key cryptography system. The standard public key sys

I'm using the method .getPublicKey() which returns public key. http://docs.oracle.com/javase/7/docs/api/java/security/cert/Certificate.html#getPublicKey%28%29 How can I know whether the key type for t

I want to get same ASN.1 output from OpenSSL as from Java PublicKey.getEncoded(). I use EC and curve type is prime256v1. Here is my code for OpenSSL: EC_KEY *ec_key = EVP_PKEY_get1_EC_KEY(key); unsign

I am using paramiko to connect to a remote server over ssh. When authenticating using a public key, the performance is slow (~90 secs). Here is the relevant logging output: 2012-05-14 17:37:21,378 Cip

I'm trying to extract a 1024-bit RSA public key from an already generated key pair (two SecKeyRefs), in order to send it over the wire. All I need is a plain (modulus, exponent) pair, which should tak

Can someone give me an example of using SSHJ for Public Key Authentication? I realise this question is essentially identical to sshj example of private/public key authentication, however the answer by

I am using SharpSSH's Sftp class to upload files. Someone has requested that I enable RSA authentication. I can't find an info how how to do this. What do I need to do in order to support public key a

I have a question about public key encryption if the the following example of how things play out is essentially correct. Then I wonder where I can find the implementations of the three algorithms whi

The following command generates a file which contains both public and private key: openssl genrsa -des3 -out privkey.pem 2048 Source: here With OpenSSL, the private key contains the public key inform

In the movie Dark Knight, the batman builds some ultra powerful sonar monitoring system and encrypts it will Null Key Encryption. I was reading this RFC but couldn't comprehend it. It says something

Is there a way to extract public key from certification using C#? I have a certification file with .crt extension.

I need to know what is public key infastructure. I need to know is this related to sending requests and response as like WsHttpbinding in WCF.

I'm trying to implement the javax.crypto encryption between my apps (through intnets). I follow this (accepted answer): How to encrypt and decrypt data in Java? .The problem is as I understood I need

I want to create random AES Encryption key (128 bit) in ios. I have searched in SO but I cannot find a good answer. Please give me some advice. thanks in advance. UPDATE: I have used BBAES lib. I used

I've generated a new public/private key pair and exported it as an XML string: RSACryptoServiceProvider RSA = new RSACryptoServiceProvider(2048); string publicPrivateKey = RSA.ToXmlString(true); The