Seuraa 
Viestejä45973
Liittynyt3.9.2015

Moi!

Luin jutun kryptografiasta, jossa salaus tehdään asymmetrisesti RSA-menetelmällä (käytössä esim. PGP:ssä). Tämän menetelmän keskeisin idea on kahden alkuluvun tulo, jonka purkaminen takaisin noiksi alkuluvuiksi pitäisi olla käytännössä mahdotonta, jos luvut ovat vain riittävän suuret. kenelläkään ei riitä laskentateho.

Muutama asia tuossa jäi kuitenkin pohdituttamaan ja sitä varten kaipaisin hieman tietoa alkuluvuista. En ole kovinkaan perehtynyt tähän aiheeseen ja siksipä kyselen ehkä hieman tyhmiäkin. Korjatkaa, jos olen ymmärtänyt jotain väärin.

Minkä kokoisia noiden kerrottavien alkulukujen tulee olla, jotta tämä riittävä salaus säilyy, 256-bittisiä? tarkoittaako tämä 256-bittinen salaus sitä, että kukin alkuluku voi olla mitä tahansa alle 2^256 (= 1.157920892×10⁷⁷)? ja jos näin on, niin montako alkulukua tuohon joukkoon ylipäätään sisältyy? Onko niitä jokin tietty prosenttiosuus lukujen kokonaismäärästä?

Kommentit (15)

pöhl
Seuraa 
Viestejä917
Liittynyt19.3.2005

Tuo RSA:n bittisyys ei ole mulle tuttua, mutta jotain sanottavaa on tuohon alkulukujen lukumäärään on.
Tarkoitat varmaan joukkoa P=\{1,2,..., 2^{256}\}. Jos p_n on n:s alkuluku,
on voimassa n ln n + n ln ln n - n < p_n < n ln n + n ln ln n kun n suurempi kuin viisi[1].

Nyt yhtälön n ln n + n ln ln n - n = 2^256 numeeriseksi ratkaisuksi saadaan Wolfram alphalla n=6.57*10^74 ja yhtälö n ln n + n ln ln n = 2^256 antaa n=6.526*10^74. Siis alkulukujen lukumäärä joukossa P on a*10^74 jollakin välin [6.52,6.57] reaaliluvulla a.

Simplex
Seuraa 
Viestejä2966
Liittynyt26.1.2010

Yleisesti PGP:n turvallisuudesta: PGP:ssä käytettävät RSA-avaimet ovat vähintään 512 bittisiä, enimmillään 4096 bittisiä. Harrastaja pystyy purkamaan 512-bittisen RSA-avaimen muutamassa viikossa. 1024-biitinen avain on jo varsin vahva tiedon salaamiseen satunnaisilta ulkopuolisilta urkkijoilta. Pidempi 2048-bittistä salausta pidetään turvallisena aina vuoteen 2020 asti, jolloin tietotekniikka on kehittynyt sen verran, että NSA saattaa saada salatun viestin murrettua.

Lähde:
http://en.wikipedia.org/wiki/RSA_%28alg ... SA_problem

Vierailija
Puuhikki
Nyt yhtälön n ln n + n ln ln n - n = 2^256 numeeriseksi ratkaisuksi saadaan Wolfram alphalla n=6.57*10^74 ja yhtälö n ln n + n ln ln n = 2^256 antaa n=6.526*10^74. Siis alkulukujen lukumäärä joukossa P on a*10^74 jollakin välin [6.52,6.57] reaaliluvulla a.



Kiitos, tämä tieto minua kiinnosti. Jäin pohtimaan sitä mahdollisuutta, että pitääkö tuo RSA-avain aina erikseen purkaa. Eikö olisi (anakin teoriassa) mahdollista laittaa supertietokone laskemaan ja taulukoimaan kaikki mahdolliset alkulukuyhdistelmät, ja sitten hakea tästä tietokannasta sopiva pari, kun tuo public key tunnetaan? Ikään kun siis tehdä tuota laskentaa etukäteen, eikä vasta kun halutaan jokin public key purkaa.

Mutta ilmeisesti tietokoneiden muisti tulee tässä vastaan. 10^74 numerosarjaa ei tai mahtua edes maailman olemassa oleville kovalevyille. Luulin, että alkulukuja on tuossa joukossa paljon vähemmän.

Onko tällaista teoriaa kukaan enempää tutkinut?

Vierailija

Teoriassa joo, mutta käytännössä ei.
Kyseisestä tietokannasta tulee niin valtava, että ei onnistu.

Rainbow kantoja lasketaan jo nykyään vähän pienimmille bittimäärille.

Lisäksi joku data voidaan kryptata useampaan kertaan joka edelleen hankaloittaa "murtamista".

Vierailija

Muuten enemmän tekniikasta: useinhan tuo vahva salaus vaatii jonnin verran tehoja, joten salatuissa yhteyksissä vahvaa salausta käytetään vain siihen että siirretään jokun kevyemmän symmetrisen salauksen avain molempiin päihin, ja tästä eteenpäin data kryptataan/dekryptataan tällä kevyemmällä menetelmällä, jolloin saadaan parempi latenssi/kaista, kyseisen session ajan.

Vierailija
artsi
Muuten enemmän tekniikasta: useinhan tuo vahva salaus vaatii jonnin verran tehoja, joten salatuissa yhteyksissä vahvaa salausta käytetään vain siihen että siirretään jokun kevyemmän symmetrisen salauksen avain molempiin päihin, ja tästä eteenpäin data kryptataan/dekryptataan tällä kevyemmällä menetelmällä, jolloin saadaan parempi latenssi/kaista, kyseisen session ajan.



Käsitääkseni juuri näin toimivat ainakin PGP ja GPG. Tosin tuo asymmetrinen salaus ei ole sen vahvempi kuin symmetrinenkään, vaan vaatii enemmän laskentatehoa algoritminsa takia. Sen etu on, että sillä ratkeaa tuo salausavaimen siirtäminen vastaanottajalle verkon yli. Ennen asymmetristen avainten aikaa tämä salausavainten toimittaminen vastaanottajalle oli valtava työ.

Vahvimman tunnetun salauksen saanee aikaan ns. "One time pad" -salauksella, joka on symmetrinen. Oikein käytettynä se on kaiketi mahdoton murtaa. Ongelmia (heikennyksiä) tuovat tosin huonot salausavaimet ja niiden hankala levitys, sekä se, että salausavain on yhtä pitkä kuin itse viestikin.

http://en.wikipedia.org/wiki/One-time_pad

Läskiperse
Seuraa 
Viestejä950
Liittynyt11.12.2010

Sulautetuissa härveleissä laskuteho on rajallista. Muistaakseni tutkin aihetta puolivuotta, ja tein 100 kryptausversiota. En enää muista, mikä niistä oli finaali, mutta ohessa on aika tehokas koodinpätkä kryptaukseen.

[code:181tig37]#include
#include
#include

/******************************************************************************
* Function: LifeCrypt *
* *
* Use: Kryptaa tai purkaa datalohkon. Ei saa kutsua suoraan, koska *
* luuppi möyhentää salaus- / purkuavaimen käyttökelvottomaksi. *
* Kutsu funktioita LifeEncrypt ja LifeDecrypt. *
* *
* Rajoitus: Latinalaisen neliön vuoksi datalohkon pituus pitää *
* olla muotoa 2 potenssiin n, ja vähintään 32 tavua *
* pitkä, koska 17 virittää 32*32 kerrannaisneliöt. *
* *
* Input: char *data on osoitin 32 tavun data-lohkoon. *
* char *key on osoitin 32 tavun = 256 bitin avaimeen. *
* *
* Output: Salaamaton data kryptataan ja palautetaan samaan data-lohkoon. *
* Salattu data puretaan samoin annettuun data-lohkoon. *
* *
* Version: 0.01 09.10.04 JAr ensimmäinen versio. *
* *
******************************************************************************/
static void LifeCrypt(char *data, char *key)
{
int i, f;
long *life;
long *apu, *upa;
long BreakUp=0x00L;

upa=(long*)(key+16);
apu=life=(long*)key;

for (i=0; i<32; i++)
{
life[0]+=(life[0]>>11)^(life[1]<<17);
life[1]+=(life[0]<<19)^(life[1]>>13);

life[0]+=life[2];
life[1]-=life[3];

BreakUp+=life[0]^life[1];
life=life==apu? upa: apu;

f=(int)(BreakUp>>28)&0x0f;
data[i] ^= (char)(BreakUp>>f);
data[i^17]^=(char)(BreakUp>>(8+f));
}
}

/******************************************************************************
* Function: LifeEncrypt *
* *
* Use: Salakoodaa datalohkon. *
* *
* Input: void *block32 on osoitin 32 tavun lohkoon. *
* const void *key32 on osoitin 32 tavun = 256 bitin avaimeen. *
* *
* Output: Salattu data palautetaan lohkoon block32. *
* *
* Version: 0.01 09.10.04 JAr ensimmäinen versio. *
* *
******************************************************************************/
void LifeEncrypt(void *block32, const void *key32)
{
char key[32];
memcpy(key, key32, 32);
LifeCrypt((char*)block32, key);
}

/******************************************************************************
* Function: LifeDecrypt *
* *
* Use: Purkaa salakoodatun datalohkon. *
* *
* Input: void *block32 on osoitin 32 tavun salakoodattuun lohkoon. *
* const void *key32 on osoitin 32 tavun = 256 bitin avaimeen. *
* *
* Output: Alkuperäiseksi purettu data palautetaan lohkoon block32. *
* *
* Version: 0.01 09.10.04 JAr ensimmäinen versio. *
* *
******************************************************************************/
void LifeDecrypt(void *block32, const void *key32)
{
LifeEncrypt(block32, key32);
}

/* ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ */
/* ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~ Testikoodia ~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ */
/* ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ ~~ ~~~ ~~ ~ */

void setBit(char *buf, int bitNro)
{
buf[bitNro>>3]|=(char)(1<<(bitNro&7));
}

void clrBit(char *buf, int bitNro)
{
buf[bitNro>>3]&=(char)~(1<<(bitNro&7));
}

int testBit(char *buf, int bitNro)
{
return buf[bitNro>>3]&(char)(1<<(bitNro&7))? 1: 0;
}

void main(void)
{
const char information[]="TimoAnitaRikuSannaRistoOlliJouni";

char CopyOfDataCrypt[32];

char key[32]=
{
0x37, 0x9b, 0x6f, 0x2c, 0x93, 0x1f, 0x74, 0x48,
0x23, 0x61, 0x31, 0x04, 0x5f, 0xb3, 0xbe, 0x2f,
0x6c, 0xcb, 0xb1, 0x2d, 0x94, 0xbd, 0x60, 0xac,
0xd0, 0x3c, 0x3d, 0x07, 0x58, 0xbf, 0xaf, 0xe0,
};

int i;

printf("256-bittinen avain on: ");

for (i=0; i<256; i++)
{
printf("%d", testBit(key, i));
}

printf("\n\n\n\n");

for (i=0; i<256; i++)
{
char data[32];
char TextBuf[32+1];
memset(TextBuf, 0, 32+1);
memcpy(data, information, 32);

printf("Salataan data...\n");
LifeEncrypt(data, key);
memcpy(CopyOfDataCrypt, data, 32);

printf("Salauksen tulos: ");
memcpy(TextBuf, data, 32);
printf("%s\n", TextBuf);

printf("Avataan data...\n");
LifeDecrypt(data, key);

printf("Avauksen tulos: ");
memcpy(TextBuf, data, 32);
printf("%s \n", TextBuf);

printf("Korruptoidaan avaimesta yksi bitti...\n");
printf("Bitti nro %d swapataan %d:sta %d:ksi\n",
i, testBit(key, i), testBit(key, i) ^ (int)1);

if (testBit(key, i)) clrBit(key, i);
else /* --------- */ setBit(key, i);

printf("Yritetaan avata data...\n");
memcpy(data, CopyOfDataCrypt, 32);
LifeDecrypt(data, key);

printf("Avauksen tulos: ");
memcpy(TextBuf, data, 32);
printf("%s \n", TextBuf);

/* Korjataan tärvelty bitti alkuperäiseksi */
if (testBit(key, i)) clrBit(key, i);
else /* --------- */ setBit(key, i);

printf("\n\nPaina nappia...\n\n\n");
while (kbhit()) getch();
getch();
}
}
[/code:181tig37]

Läskiperse
Seuraa 
Viestejä950
Liittynyt11.12.2010

Ota funktio getch() pois, jolloin kirjastoa ei enää tarvita.

Konsoliversiossa getch:in tilalla pitäisi olla jokin odotusfunktio, muutoin luuppi tulostaa kaikki 256 testitapausta vilahduksena.

pöhl
Seuraa 
Viestejä917
Liittynyt19.3.2005

Nyt sain kääntymään ja näkymään kun poistin getchit, mutta ilmeisesti koodi ei ole nyt enää standardin mukaista. Vielä tuli käännösvaroituksia seuraavasta kohdasta:
[code:6ic9gofa]char key[32]=
{
0x37, 0x9b, 0x6f, 0x2c, 0x93, 0x1f, 0x74, 0x48,
0x23, 0x61, 0x31, 0x04, 0x5f, 0xb3, 0xbe, 0x2f,
0x6c, 0xcb, 0xb1, 0x2d, 0x94, 0xbd, 0x60, 0xac,
0xd0, 0x3c, 0x3d, 0x07, 0x58, 0xbf, 0xaf, 0xe0,
};[/code:6ic9gofa]
[code:6ic9gofa]
jaakko@jaakko-VPCEB1S1E:~/Desktop$ gcc -Wall -pedantic test.c
test.c: In function ‘main’:
test.c:117:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:117:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:118:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:118:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:119:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:119:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:119:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:119:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:119:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:120:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:120:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:120:7: warning: overflow in implicit constant conversion [-Woverflow]
test.c:120:7: warning: overflow in implicit constant conversion [-Woverflow]
[/code:6ic9gofa]

Läskiperse
Seuraa 
Viestejä950
Liittynyt11.12.2010

Riippuu kääntäjän varoitusasetuksista. Viittaisi johonkin etumerkkilaajennusristiriitaan. Ei kovin hieno korjaus, jos joka arvon kastaa erikseen char:ksi.

[code:1sdbgevc]char key[32]=
{
#define X (char)
X 0x37, X 0x9b, X 0x6f, X 0x2c, X 0x93, X 0x1f, X 0x74, X 0x48,
X 0x23, X 0x61, X 0x31, X 0x04, X 0x5f, X 0xb3, X 0xbe, X 0x2f,
X 0x6c, X 0xcb, X 0xb1, X 0x2d, X 0x94, X 0xbd, X 0x60, X 0xac,
X 0xd0, X 0x3c, X 0x3d, X 0x07, X 0x58, X 0xbf, X 0xaf, X 0xe0,
#undef X
};
[/code:1sdbgevc]

Vierailija

Jos laskentateho on rajallista, niin eikö olisi fiksua säätää tuota kryptaamisen tasoa lähdemedian tyypin mukaan? Esim valokuvan kryptaaminen ei (kai) vaadi lainkaan niin vahvaa avainta kuin teksti. Kuvittelen näin siksi, että valokuvan data on jo lähtökohtaisesti jo aika satunnainen, joten sen purkaminen millään loogisella algoritmilla on vaikeaa. Teksti on taas täynnä kielen loogisuuksia, joiden avulla sitä yritetään purkaa, esim. sanojen tai kirjainten esiintymistiheyden avulla.

Simplex
Seuraa 
Viestejä2966
Liittynyt26.1.2010
Läskiperse
Riippuu kääntäjän varoitusasetuksista. Viittaisi johonkin etumerkkilaajennusristiriitaan. Ei kovin hieno korjaus, jos joka arvon kastaa erikseen char:ksi.

[code:1ua2tcza]char key[32]=
{
#define X (char)
X 0x37, X 0x9b, X 0x6f, X 0x2c, X 0x93, X 0x1f, X 0x74, X 0x48,
X 0x23, X 0x61, X 0x31, X 0x04, X 0x5f, X 0xb3, X 0xbe, X 0x2f,
X 0x6c, X 0xcb, X 0xb1, X 0x2d, X 0x94, X 0xbd, X 0x60, X 0xac,
X 0xd0, X 0x3c, X 0x3d, X 0x07, X 0x58, X 0xbf, X 0xaf, X 0xe0,
#undef X
};
[/code:1ua2tcza]




Miksei helpommin unsigned char key[32] = etc.? Jos kirjoitatte koodia C/C++:lle, niin opetelkaa edes tietotyypit. Tietotyyppiä char ei pitäisi käyttää milloinkaan, vaan tyyppi tulee määritellä aina joko signed char tai unsigned char. Syyn hakeminen edellä kerrotulle jätetään harjoitustehtäväksi. Mitä tietotyyppeihin tulee, niin ohjelmissa tulisi aina määritellä tarpeen mukaan tyypit uint8, uint16, uint32 ja uint64, sekä int8, int16, int16, int32 ja int64. Lisäksi, tulisi miettiä varsin tarkkaan ennen kuin lähtee esim. vertailemaan etumerkillisiä ja etumerkittömiä lukuja keskenään. Jos ei osaa ohjelmoida, suosittelen siinä tapauksessa Adaa. Siinä on sentään hieman yritetty suojella ohjelmoijaa ihan triviaaleilta virheiltä ja järjettömyyksiltä.

Simplex
Seuraa 
Viestejä2966
Liittynyt26.1.2010
Puuhikki
Simplex
Tietotyyppiä char ei pitäisi käyttää milloinkaan, vaan tyyppi tulee määritellä aina joko signed char tai unsigned char.

Toisenlaisiakin mielipiteitä on olemassa. http://stackoverflow.com/questions/7519 ... igned-char



Totta tuo. Merkkijonojen esittäminen char-tyyppinä onnistuu yleensä. Mutta silloinkin merkkien tai merkkijonojen vertaaminen keskenään saattaa tulla mielenkiintoiseksi riippuen kääntäjästä. Miksi näin? Se jääkööt jälleen harjoitukseksi, mutta voin antaa vinkin: 8-bittinen ASCII-taulukko. C-kielen runtime-kirjaston merkkijonofuntioissa käytetään valitettavasti tyyppiä char, mikä on tuonut mukanaan historiallista painolastia ja saattaa aiheuttaa kiusallisia debuggaustilanteita, kun ohjelma saattaa toimia oikein tietyllä kääntäjällä käännettynä ja toimia virheellisesti toisella kääntäjällä käännettynä.

Suosituimmat

Uusimmat

Uusimmat

Suosituimmat