EGE/RSA

Wiki-Quelltext dieser Seite.

[[Bild:schema_rsa.png]]
== Entwurf öffentlicher Schlüssel (e, N) ==
Lege zwei (große) Primzahlen <math>p</math> und <math>q</math> fest mit <math>p \neq q</math>.

Bilde das Produkt <math>N = p \cdot q</math>.

Suche eine weitere Zahl <math>e</math>, für die gilt:
* <math>e</math> ist Primzahl und größer als <math>p</math> und <math>q</math> <u>oder</u>
* <math>e</math> ist teilerfremd zu <math>(p-1) \cdot (q-1)</math>.
Die Zahlen <math>e</math> und <math>N</math> bilden den ''öffentlichen Schlüssel''.

== Entwurf privater Schlüssel (d) ==
* <math>d \le (p-1) \cdot (q-1)</math> <u>und</u>
* <math>(d \cdot e) \bmod [(p-1) \cdot (q-1)] = 1</math>

== Bob verschlüsselt die Nachricht M ==
Voraussetzung: öffentlicher Schlüssel (e, N)
Ein Klartext-Zeichen mit dem Code <math>M</math> wird mit
<blockquote><math>M^e \bmod N = C</math></blockquote>
zu <math>C</math> ''verschlüsselt''.

== Alice entschlüsselt die Nachricht C ==
Voraussetzung: privater Schlüssel d, öffentlicher Schlüssel N, Code C
Der verschlüsselte Code <math>C</math> wird mit
<blockquote><math>C^d \bmod N = M</math></blockquote>
zum Code <math>M</math> des Klartext-Zeichens ''entschlüsselt''.

== Hausaufgabe ==
RSA-Faktoring-Chalenge (Wikipedia) lesen
* Warum ist das RSA-Verfahren mit kleinen Primzahlen immer noch unsicher? (Wozu benötigt man möglichst große Primzahlen?)
* Was bedeutet 205 Bit?
* Wie groß sollten zwei sichere Primzahlen sein?

<!--[https://vimeo.com/114048258 RSA mit dem Android-Handy] ansehen und versuchen, umzusetzen.-->

== Wir verschlüsseln uns Nachrichten gegenseitig ==
=== Tim ===
N = 2951496213141662331323665053128112557378911707093713492954789957537231681683032654203439442684989259303550465631213589388871323904730918478024673146050974374184029991675195149432744206146108231886549386552991581064377450979852881966895979134531826358941364454722375485044829485265639664011582319334250043031090676544576122883714970235494357318190231720540246670794151681100977732757063290446580710379323044482215917092131909505882464099680214817217724378706043017975599248131170828138859232153415378355650370118143644321361592959242030885583046225895822976010539797767795394679615254227265607237235751274593784154359271251377725420277154394575958222944682111911211201371796566162188091071630490817110562029081042512031938343752630633952255937686764881299400473306362144718149647792841490514356878964237845723962222797432389858238988839172814221863479717960538033372044532184979436259862897653773907177479210498264909262465138168256151148061508449980215896368187781716992848221547972841419916470928479327781180557556631138303960489900944303699112595506096217465711547212154899627239692182547617840348139493302730431981881993263227630518100429366221858075213461994946334604694591132001941108521807543438026992971556601021266606190130121

e = 2^16+1

1) 2392224459871828915041138653819651437883711117792746758435005777272266397058246475673863870825613037122370514985984850879580657341245535983044748962732061971626459001311509916793375588005942125612142491747166631193332625308962621091512919440369176875007257512259029772123241973196954843995515743022079706710836362583655996107071911693671690264018948558388283547128640307015898701406790573361674406417677694137770605087789495250969339181374515753572992636383697509758764128523662432717187661112758685767579196230179057950548475041049914997943500538070501135550083570549833335271348135092591604605014624443930362166649030644084001790883987250606544454665515352128931512894790097008893681235672615013777328451363321217989622627323078677190722630772137922383768352750497521330258532075112458202544679792806946363268675306442989696234826522453019031913976364163918591333051682822797405733502002730935320241431482376183306138641589791812556281769064168422916563729737834198908102704696609689563703004994786598605713733005751451481125549258944351248454691105501478044154640548687041685999060635154184586331686525908193395696379100946075013575606676736766251275120428369883210633953178163442995699774758912199228245198164130741358610943832684

Für Tim

1756770330185630487594721446384750465829221274400587480800055721400658346269991460035248064348939233992024230399016564251427780082505315610192431622620535650799198788804817878278428794060242165384329477864747916665037345889928527037450303618288679646381853837915567268833466145953596744508963992013537530338464618032117249907221162367848427999417551688583750185128548770381506995167835904485480931693990410803085476125552221774490523685365691457895903670943418028271807120646437407799063340814474868380596057719054407130735254063401783989182489619806237153227376142139611434090848208889905452343659294895470673318147287275437664116139317317274693321547818143620987491054705879565409465536851681501389309114872072559172055418541349552347431327631220909920682094224125483751350674118795555285782272611209730564808530924471199998895992579628479619649001116123944843209083442295173326123770734751767781927034499627319306393364168402387830493991596135787937687082961527959622186477479102748148033675318648701909647290695087402328894764323881960194700715158600816980955089137106511449354131903704544715167062024205271568581964006677190054115117594664339547546264368254884074878506860054314532610487344953710322760908932364965518084870529322

neue Nachricht:
2763265283241694707562918726015478520320371570106621520241748284059793200780630436646132944848048754520298425492002980875214197925373435317607895574042234535646038518984686409260685908193088560240553309012118166834122584469653872293662170993634477404976978735165045932655228513764785479912468741796621141593117148240272860846281402179628067155520016388947386352077200088326833987918469212648021446187193579217678503049440114404219776114945411051225143705030541946844076017914631488964220401751232491208839102000458523892997019882791993536753660842581667540533708903130300931888995039924355475840295399653047817056398422923664726860758147907594690722855810354838480093878597682231354602589415603208504026889923439054839849348070230356409455792442740690885967733780833905548327995859241331080974668509276490752784218225600321566012256239539273248236051557082928897237112087270502872271708711671987907453025713122658685539078134628595839090601167319384496349583149246861741058497039827570771146573041001503354371216979625302574486241167879422780700865294698206648925976614185655588206075549236991910925976948367980405516616883982668733548125600827603141103656181298079705026869336198640534344537888551056141154139794392318352735420323602

=== Elise ===
N 2923723657325689753
e 2^16+1
Text 0322250827748490414 # 2472611229660409538

=== Aaron ===


N = 342956342295936292393891065641893848736794637392384905846248337168707372110193242555224205908083853003936877171398504438871986838061794089548556100318210498605169358697424178879588021755612930564718472506596932823230019829866898431511462092089434738834527839804259638587300757080878235961034877974398932419717896844890407447523692489085985424359033716736427251766485939060462261977410038006304484567526310806073451518012344047187124975235095714852025089810499097090019126147158689387795694419416576325671900858438121477483191429974749171009612676629191146199083808915894262866730712099283829536472869745453743653167884015024512206141635707412928017716264949359671943789198041161042941651281295446900810333075345070608798890527450157990047573623084580225697893846731057482172911313132340399681162714965981849334320087057013071241614799747150834558042270003477076231395504907830736251029928211875938700992659340699686674266703250431331739179054250196877807829441300900162682165577845533899425139

e = 2^16+1



Nachricht: 126304627608289288230483148932089763700911183104948167036713152179022837333903741695555704073243773922711693065653122052509559372342287147514914919457888710314018861798214534377963509699117409512392751741663805102106574328871045476319607726450468746777766896541707431347197078795243587414473062698311067530195902944516634755353122911231343750861937718450507960141431355552312538306344393685667930829336714463785339113003290231070049959334192654587644371452107376705180051481438561228074357715549501682821335954542543163192044059171440746551217839143880023541464953656664537667646996869810935870989669500517736575064868464947886721515896537033394244999021425542175015347956952704767015988855780516323539999145277525115303267311660076514642651905438614724565570127786940268222004055554397111289435419640837149138764769902763443542338753116531722439383585766063989726812787986468978931541633347840290071405336547570922294433066000767902446291416659647887725108558880810746856274908959776867386223

=== Johannes ===
N=11760947285600722187007680388822169352914722465775663150025873219726620452322667698132003203338515849237082308349304176952629313528265414313128730488183827530712411157595645803419296408218651422365099661623318457186024029604386968344431558489090063989728309774779347231327615016603461436632461151863962301612360958863821815340312889410091326699571030352854508094555162079295364678646685290162820082795753995603758063927961372710021863900935035938896780135413270023549296782562739748213230240956398866639350995797975668163553986829881512698431661191328176839894359841733166089569856937344296203654146921847600353676479

e= 2^16+1

=== Dandy ===
N = 1688180727500347741

e = 65537

Schlüssel für Josef: 1234120474465912099 # 1230353083399707634 # 0462960430889572536 # 1668559233401989181 # 0558528854443029121 # 0061871616029764787 # 1433346339072452767 # 0197958887340782944



NEUES N: 70313059467932863650169950936591565248388630662268540577171426278710028722595972264074667753231715421602362044623199540558837571477071006385223272585194864727758823723363967365015529293171819326248730074249401342569750344511699494229111082865475344604279641227176985435756309410186029080389810872928399150596276996577278698614619434466713766369267319034270346313522879773243476720004777695933246705455221495249461522498937603515923818161571063793269519622612555578346508550406497713662914147387067822963264081898155885513293859099084743803993977664963035440168382471722577533736377750321721078751825224181296308321319

Nachricht:

19262975724321163295339439280478656381964237844081563434965683329905181695957669779127644525554847341992274889006923112026369061838494934613182071229111262041514884497216696151001608613718258338743316298522435145266184816881384022899228271525953236133998521859910669026000743045241705895147125167012062695750326964568375419001332487595417233432385444721461852799465236299225356546833830897155880416661821154740971963530667939939434925736278347141479276623993690974582570241279710346578721445132657655881342331327740308262310901240171134530585388929160505609833232814636901314877709410548384980648159784945514229802132

Nachricht von Johannes: 7672165836307934833397910382884863298573313528179342317465046177391876116086590314191676381300187115849970279001137858758454782815139020831284669727051494007507714503772352618832502672160752153096956080726680158499899845621591477811356848817538550900155772953828604880546410771616149609646444328289915671788522385664885183831975675860380143394494960118865104436379641523656251851748853068987225002772851975792345770835574384979576010469800480332692466632463214563691481603434276730106082930028495763660764918384779775009008725875932344829143155847323000910415710628965614333835860065088086817324886077464959141759327

=== Josef ===
N = 70313059467932863650169950936591565248388630662268540577171426278710028722595972264074667753231715421602362044623199540558837571477071006385223272585194864727758823723363967365015529293171819326248730074249401342569750344511699494229111082865475344604279641227176985435756309410186029080389810872928399150596276996577278698614619434466713766369267319034270346313522879773243476720004777695933246705455221495249461522498937603515923818161571063793269519622612555578346508550406497713662914147387067822963264081898155885513293859099084743803993977664963035440168382471722577533736377750321721078751825224181296308321319

e = 2^16+1 bzw. (65537)


Sie wurden von Dandy angestupst: 00039185256248991460625831862675631167425754307480848380243916623725330809811147982560011477041693231251133451855244006038523668051497023314018557280318922883757698101720772136460580513611947572035371235190358623406989433407528521402316831714775580367692919955094892196755801256448608955044716464997790422712921730831359967021407580112728499341676000355534002158137734716514216813404535329165931304692369769582447147577329310583373419456126625174502795174459301014369550277200196023652796833547699768243913253471078667743309345442404376378293550048528643961544593169856167997124705569367143817211283074910542172366259

*stups*:
48508924652534148633957957667333918418052814555757800997608842691052706161294369804529343179859261796038002949101521697709396604518648124348211181690634997220992371918337164117893435825178441974559583163327822500881918786036341446460620375158966612940582433390606232654167937248125709026247831461346805533255347466006851606513958862609495558282033514338000508927847143746637232350789886327252379022722889886164023933345115302361608024436526790270602012448841437803457993471434592814295155980488961312262006403948723470200948397496749427211434718356725626861466830325571182464707315343126317059679626455005452894496638

=== Theresa ===
N=2189329218283721051
e=2^16+1

1 neue Nachricht von Heidi:0960431449687320593 # 1321373400322207727 # 0782940085349524221 # 0386420003740380966 # 0537310695899918429 # 0873795174461400411 # 1767094842803462446 # 0107150302338772149 # 0332336724158767107 # 1819778149649941543 # 0684844835086246406 # 1646236126423120900 # 2118456125486013924 # 2023364804533987443 # 0975267753970930938



N:15183535067973043775902927922501891828758476465483949271799394753796564506503677251445488834169484405501788394169343007025864024592808285180020872962809716389406002425172368297310701034782115590878490160203868260340974945722404692392161782048045772932045290570895180610096913216606520767995969534690907604094400257472521594975880551236595567772039939646435991517050289484539898862769465721223051027963879068114532623914723127952707167386044780678127178359913995372635862297197646779268356891225250522165310128571709974918475559333197657002918521392021934078325555691680390351385912391208373997646501543451114534424347716863872516732532046974817228496759968566138189804176461196304349483367953868209882396263941475791741891

e:2^16+1

=== Heidi ===

verschlüsselte Nachricht:

1136011545364292294 # 1061740183986791317 # 2111626553460064403 # 2368350865761515465 # 1105560748490278701 # 0232785873229391537 # 2094094700269354771 # 0426665001269638855

Neue Schlüssel:
e: 2^16+1

N:117268854531128040260967383142514277109843890173806353133471620976403308786068461288210900674015375788577160507579466445975785812923855040310477327405502825741150460341026586798585116551129308054861649639514187278135603533905017942167306166249942256766578954013204334164845450170143548896945922930394524028566771578253917234381759472505479961400118027105906277078687113917759952392254850180031760727575288788268195649993221977236318471813403104681373569942814068251138929983181615343448472696971157522433614355883248346986167411607611140298755763068527216016897514028449428615484749196960754170437262884832791490976943151382287370589843522481110479323480134033272891042008586425172543178869182030421724121016938009703710790900651225603186984399251541570700889777392175670522183978046181015108751728589783476564092924993062153062093233506683743564519288953940104915073798237672870513308048377994504892825620119293375229110036446218209725864189233150845394370013451581067926351643151224374825610667016369507533376812746676735050172749935604254472171581062733875527531894555458753378200309591460276050163137960961625918708815589378190039343399085551540666909505752548219236578363126290485493385176657813881081932373762238502505205389413

eine neue Nachricht von Theresa:

00191484979560424978127680436972096332345332342803576192670016966672264807129093793705166348408134422075954884780664110038508743969578312070974379275011244621675314907294675274272748974743183143926947087188087465052159000155651862039258234823985285007064829440896009894264550503999316033179177960972051122035671770551318586996895556319943548476481437689808530444903500121872318782185791748740979285095367562407690896040740741675447069792221739345260918069429567192711463661326793318113523961951296507395610430796642559684283303069576098328784077809021180631583234918035626674429384661738441760537593789197933343622808554961663905262278442087778112537341834639412492580201146669919718474535722260477688161669710567121131908961250016538565233080849990412315277244101900850451848057952422963984670167781897688180596045034589311886546214167792402699572422524701615452851098754717044479180639201077531069904622156889164408574086344184472239147601542242700013477468198265439890286594116011523289001601050056773016663462692387943149083158925989313912351271822996391375983896783581754712934394931316721658487839732279919435337027495663448779423596729641040689516594798550155350933741653837960471233691116505300938284003618499989791538509443